Binary Search

Overview

Property	Value
Best Case	$O(1)$
Worst Case	$O(\lg n)$
Aux. Memory	$O(1)$

A recursive solution looks as follows:

static int aux(const int needle, const int i, const int j, int *A) {
  if (i > j) {
    return -1;
  }
  int mid = (i + j) / 2;
  if (A[mid] == needle) {
    return mid;
  } else if (A[mid] < needle) {
    return aux(needle, mid + 1, j, A);
  } else {
    return aux(needle, i, mid - 1, A);
  }
}
 
int binary_search(const int needle, const int n, int A[static n]) {
  return aux(needle, 0, n - 1, A);
}

We can also write this iteratively:

int binary_search(const int needle, const int n, int A[static n]) {
  int i = 0;
  int j = n - 1;
  while (i <= j) {
    int mid = (i + j) / 2;
    if (A[mid] == needle) {
      return mid;
    } else if (A[mid] < needle) {
      i = mid + 1;
    } else {
      j = mid - 1;
    }
  }
  return -1;
}

Bibliography

• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).