Binary Search

Section 13.3 Binary Search

The binary search algorithm is a highly efficient search algorithm used to find a target value within a sorted collection or array. It follows a "divide and conquer" strategy, repeatedly narrowing down the search range by comparing the target value with the middle element of the current range. This algorithm is particularly useful when dealing with large datasets, as it reduces the search space exponentially with each comparison.

The binary search algorithm works as follows.

Input: The algorithm takes two inputs: the target value that you want to find and the sorted sequence or array in which you’re searching for the target value.
Initialization: Start with the entire range of the sorted sequence, from the first element (index 0) to the last element (index N-1), where "n" is the number of elements in the sequence.
Midpoint Calculation: Calculate the midpoint of the current range by finding the average of the first and last indices:
```
midpoint = (first_index + last_index) / 2
```
Comparison: Compare the value at the midpoint with the target value.
1. If the value at the midpoint is equal to the target value, the search is successful, and you’ve found the target value. The algorithm terminates.
2. If the value at the midpoint is greater than the target value, narrow the search range to the lower half of the current range (from the first index to the midpoint - 1).
3. If the value at the midpoint is less than the target value, narrow the search range to the upper half of the current range (from the midpoint + 1 to the last index).
Repeat: Repeat steps 3 to 5 until the target value is found or until the search range becomes empty (i.e., first index is greater than last index).
Termination:
1. If the target value is found, the algorithm returns the index of the element where the target value was found.
2. If the target value is not found after the search range becomes empty, the algorithm indicates that the target value is not present in the sequence.

The binary search algorithm’s key advantage is its time complexity. In each step, the search range is halved, leading to a time complexity of \(O(log N)\text{,}\) where \(N\) is the number of elements in the sequence. This makes binary search significantly faster than sequential search for large datasets. However, it’s important to note that binary search requires the sequence to be sorted, and its implementation might be slightly more complex compared to sequential search.

In Listing 13.3.1, the binarySearch(…) function takes a sorted array (arr) and a target value (target) as parameters. It uses the binary search algorithm to find the index of the target value in the array or returns -1 if the target is not found. The main method demonstrates the usage of the binary search function on a sorted array.

public class BinarySearch {

  // Binary search function
  static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (right >= left) {
      int mid = left + (right - left) / 2;

      if (target == arr[mid]) {
        return mid;         // Found the target
      } else if (target > arr[mid]) {
        left = mid + 1;     // Search in the right half
      } else {
        right = mid - 1;    // Search in the left half
      }
    }

    return -1; // Target not found
  }

  public static void main(String[] args) {
    int[] sortedArray = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
    int target = 23;

    int result = binarySearch(sortedArray, target);
    if (result != -1) {
      System.out.println("Target " + target + " found at index " + result);
    } else {
      System.out.println("Target " + target + " not found in the array.");
    }
  }
}

Listing 13.3.1. BinarySearch.java

javac BinarySearch.java
java BinarySearch
Target 23 found at index 5

Note that on each iteration of the binary search algorithm, as the problem size narrows, smaller versions of the problem are solved. This makes binary search a good candidate for a recursive implementation. Listing 13.3.2 is an alternative recursive implementation of binary search. Note how we overload the recursiveBinarySearch(…) method with a version that defaults the search range to the entire array.

// Recursive binary search helper function
public static int recursiveBinarySearch(int[] arr, int target) {
  return recursiveBinarySearch(arr, target, 0, arr.length - 1);
}

// Recursive binary search function
public static int recursiveBinarySearch(int[] arr, int target, 
                                        int left, int right) {
  // Calculate midpoint index
  int mid = (left + right) / 2;

  if (left > right) {
    return -1;               // Target not found
  }
  else if (target == arr[mid]) {
    return mid;              // Found the target
  }
  else if (target > arr[mid]) {
    left = mid + 1;         // Search in the right half
  }
  else {
    right = mid - 1;        // Search in the left half
  }
  // Recursively search in smaller range
  return recursiveBinarySearch(arr, target, left, right);
}

Listing 13.3.2. Recursive Binary Search Implementation

Computational Problem Solving with Java and Interactive Object Graphics

Search Results:

Section 13.3 Binary Search