Binary Search

Table of contents

1. In a Sorted Array
   1. Iterative Search
   2. Recursive Search

In a Sorted Array

Our objective is to find the index of a target element in a sorted array.

block-beta
  columns 11
  idx 0 1 2 3 4 5 6 7 8 9
  elem A B C D E F G H I J

You’re going to be chopping up the array in half repeatedly.

In both iterative and recursive versions, you need to keep track of the left and right bounds of the search.

Iterative Search

Start with the basic setup:

int IterativeSearch(const vector<int>& arr, int target) {
  int n = static_cast<int>(arr.size());
  int left = 0, right = n - 1;
}

The loop condition is left <= right.

Inside the loop, repeatedly check if the middle element is the target. If not, adjust the bounds accordingly.

If you’re undershooting, move on to the right half. If you’re overshooting, move on to the left half.

while (left <= right) {
  int mid = left + (right - left) / 2;
  if (arr[mid] == target) return mid;
  if (arr[mid] < target) left = mid + 1;
  else right = mid - 1;
}

return -1;  // Not found

Recursive Search

Works the same way, just expressed as a recursion.

int RecursiveSearch(const vector<int>& arr, const target, int left, int right) {
  if (left > right) return -1;

  int mid = left + (right - left) / 2;
  if (arr[mid] == target) return mid;
  if (arr[mid] < target) return RecursiveSearch(arr, target, mid + 1, right);
  return RecursiveSearch(arr, target, left, mid - 1);
}

Complexity of both versions is $O(\log n)$.