# 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.

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
}
}

}

// 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.