Binary Search Algorithm

Imagine looking up a word in a dictionary. You don't start at page one. You flip to the middle, see if the word comes before or after, and halve your search. That's binary search.

What It Does

Binary search finds a target in a sorted array by cutting the search space in half with every step. Instead of checking every element (O(n)), it gets there in O(log n).

For an array of 1 million elements, linear search might take 1 million steps. Binary search takes at most 20.

The Code

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

const sorted = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
console.log(binarySearch(sorted, 23)); // 5
console.log(binarySearch(sorted, 50)); // -1

How It Works Step by Step

Searching for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]:

1. left=0, right=9, mid=4 → arr[4] is 16 < 23 → search right half
2. left=5, right=9, mid=7 → arr[7] is 56 > 23 → search left half
3. left=5, right=6, mid=5 → arr[5] is 23 → found it

Three steps instead of six.

Complexity

• Time: O(log n) — halving the search space each iteration.
• Space: O(1) for iterative, O(log n) for recursive (stack frames).

The Catch

Binary search requires a sorted array. If the data isn't sorted, you either sort it first (O(n log n)) or use linear search.

Also, watch out for integer overflow on (left + right) / 2 in languages without arbitrary precision. JavaScript handles it fine, but in C++ or Java you'd want left + Math.floor((right - left) / 2).

The Trade-off

Binary search is fast but rigid — it only works on sorted data. If your data changes frequently, maintaining sort order on every insert might cost more than the search savings. In that case, consider a BST or hash map instead.