Binary Search

Binary Search is a divide-and-conquer algorithm that searches through a sorted list for a target value, returning the index of the target value if it exists. The algorithm works by repeatedly dividing the search space in half until the target value is found or the search space is empty. It is one of the most basic algorithms when studying divide-and-conquer algorithms.

Time complexity analysis

Because the search space is divided in half at each step, the time complexity of Binary Search becomes .

Space complexity analysis

Because BinarySearch does not allocate any additional memory space, the space complexity is constant of

Implementation

Java Implementation

package jun.codes.interviews.search;

public class BinarySearch {
  public static <T extends Comparable<T>> int search(T[] xs, T target) {
    return search(xs, target, 0, xs.length - 1);
  }

  public static <T extends Comparable<T>> int search(
      T[] xs,
      T target,
      int low,
      int high
  ) {
    // If the low and high indices have not crossed each other, then we can
    // continue the search. In other words, there are more items to search
    // through.
    if (low <= high) {
      // Split the search space in half
      int midpoint = (low + high) / 2;
      // If the midpoint is the target, then we've found the index. Otherwise,
      // we search the relevant half of the search space.
      Integer comparison = xs[midpoint].compareTo(target);

      return switch (comparison) {
        case 0 -> midpoint;
        // If the midpoint value is greater than the target, then we need to
        // search the lower half
        case Integer x when x > 0 -> search(xs, target, low, midpoint - 1);
        // If the midpoint value is less than the target, we need to search the
        // upper half
        default                   -> search(xs, target, midpoint + 1, high);
      };
    }

    return -1;
  }
}

Further reading

The relevant material in Introduction to Algorithms 4th edition can be found starting on page 17.

• Wikipedia: Binary Search