Binary Search Implementation (Iterative and Recursive) - Java Solution

1. Introduction

In this post, we'll dive into one of the most fundamental algorithms in computer science - Binary Search. We will implement binary search in Java using both iterative and recursive approaches. This algorithm is essential for efficiently searching a target element in a sorted array.

Problem

Given a sorted array of n elements, find if a given element target is present in the array.

2. Solution Steps

Iterative Implementation:

1. Initialize two pointers, low and high, to the start and end of the array.

2. While low is less than or equal to high, calculate the mid-point.

3. Compare the target with the mid-point value.

4. If they match, return true.

5. If the target is less than the mid-point, adjust the high pointer.

6. If the target is more, adjust the low pointer.

7. If the target is not found, return false.

Recursive Implementation:

1. Base case: If the range is empty (low > high), return false.

2. Calculate the mid-point.

3. If the target matches the mid-point, return true.

4. Recur either on the left half or the right half of the array depending on the target's relation to the mid-point.

3. Code Program

public class BinarySearch {

    // Main method for testing
    public static void main(String[] args) {
        int[] array = {2, 3, 4, 10, 40};
        int target = 10;
        System.out.println("Iterative: Target " + target + " found: " + iterativeBinarySearch(array, target));
        System.out.println("Recursive: Target " + target + " found: " + recursiveBinarySearch(array, 0, array.length - 1, target));
    }

    // Iterative binary search
    public static boolean iterativeBinarySearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == target) {
                return true; // Target found
            } else if (arr[mid] < target) {
                low = mid + 1; // Adjust low pointer
            } else {
                high = mid - 1; // Adjust high pointer
            }
        }

        return false; // Target not found
    }

    // Recursive binary search
    public static boolean recursiveBinarySearch(int[] arr, int low, int high, int target) {
        if (low > high) {
            return false; // Base case: range is empty
        }

        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return true; // Target found
        } else if (arr[mid] < target) {
            return recursiveBinarySearch(arr, mid + 1, high, target); // Search in right half
        } else {
            return recursiveBinarySearch(arr, low, mid - 1, target); // Search in left half
        }
    }
}

Output:

Iterative: Target 10 found: true
Recursive: Target 10 found: true

Explanation:

Both the iterative and recursive implementations of binary search aim to find the target element within the sorted array [2, 3, 4, 10, 40]. In our test case, the target element 10 is present in the array. 

The iterative version uses a while loop to halve the search space at each step, while the recursive version achieves the same via recursive calls. 

Both methods have a time complexity of O(log n), making them highly efficient for large datasets.