Binary Search

Binary search is one of the most important algorithms to have at your fingertips. It solves a deceptively simple problem — finding a value in a sorted collection — in O(log n) time by halving the search space with each comparison. That’s the difference between searching through a billion sorted entries in roughly 30 comparisons vs up to a billion.

The Precondition: Sorted Input

Binary search only works on sorted data. This seems obvious but is the single most common mistake: applying binary search to unsorted data produces wrong answers with no error.

IMPORTANT

Always verify the input is sorted before applying binary search. If sorting is required first, the overall complexity becomes O(n log n), not O(log n).

How It Works

Given a sorted array and a target value:

Look at the middle element.
If it equals the target, return its index.
If the target is less than the middle, search the left half.
If the target is greater than the middle, search the right half.
Repeat until found or the search space is empty.

Iterative Implementation

function binarySearch(arr: number[], target: number): number {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    // Use Math.floor instead of (low + high) / 2 to avoid integer overflow
    // (in TypeScript/JS this isn't a practical concern, but it's good habit)
    const mid = low + Math.floor((high - low) / 2);

    if (arr[mid] === target) {
      return mid;       // found
    } else if (arr[mid] < target) {
      low = mid + 1;    // search right half
    } else {
      high = mid - 1;   // search left half
    }
  }

  return -1; // not found
}

Recursive Implementation

function binarySearchRecursive(
  arr: number[],
  target: number,
  low = 0,
  high = arr.length - 1
): number {
  if (low > high) return -1; // base case: not found

  const mid = low + Math.floor((high - low) / 2);

  if (arr[mid] === target) return mid;
  if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, high);
  return binarySearchRecursive(arr, target, low, mid - 1);
}

NOTE

The iterative version is preferred in practice because it avoids the function call overhead and can’t stack overflow. The recursive version is useful for understanding the algorithm’s structure.

Off-By-One Traps

Off-by-one errors are the #1 bug in binary search implementations. Here are the two critical choices:

Decision	This code	Why
Loop condition	`low <= high`	We must check when `low === high` (one element left)
Left half update	`high = mid - 1`	`mid` is already checked, exclude it
Right half update	`low = mid + 1`	`mid` is already checked, exclude it

If you write low < high, you’ll miss the last element. If you write high = mid, you can get an infinite loop when low === mid.

CAUTION

while (low < high) vs while (low <= high) — this single character causes hours of debugging. When in doubt, think through the single-element case: if low === high, is there still a valid element to check? Yes. So use <=.

Binary Search in the Real World

Binary search isn’t just for “find a number in an array.” It generalizes to any problem where:

You’re searching over a monotonic space (answers go from false to true at some threshold)
You can evaluate mid in O(1) or O(log n)

Common applications:

Finding the first/last occurrence of a value
Finding the insertion point for a value in sorted data (Array.prototype doesn’t have this, but it’s a classic interview question)
Searching a sorted matrix
Binary searching on the answer (e.g., “what’s the minimum number of days to complete X?”)

Further Learning

Search these terms to go deeper:

“Binary search on the answer technique competitive programming” — powerful generalization beyond simple array search
“Leetcode binary search explore card” — structured practice problems from simple to advanced
“lower_bound upper_bound C++ STL binary search” — first/last occurrence variants built into standard libraries
“Extra, Extra — Read All About It Nearly All Binary Searches Broken” — classic blog post on the integer overflow trap

Binary Search

You’re looking for a word in a dictionary. You don’t read from page 1 — you flip to the middle, see if your word comes before or after, and throw away half the book. Repeat. That’s binary search: by halving the search each step, it finds an item among a billion in about 30 checks.

The one rule: the data must be sorted

Binary search only works on sorted data. That’s the whole catch — on an unsorted list it gives wrong answers silently.

IMPORTANT

Always make sure the list is sorted first. If you have to sort it yourself, that sorting costs O(n log n), which may cancel out binary search’s speed advantage for a one-off lookup.

How it works

Look at the middle item.
Is it your target? Done.
Is your target smaller? Throw away the right half; search the left.
Is it bigger? Throw away the left half; search the right.
Repeat until found (or nothing’s left).

Each step deletes half the remaining items — that’s why it’s so fast.

The code

function binarySearch(arr, target) {
  let low = 0
  let high = arr.length - 1

  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    if (arr[mid] === target) return mid      // found it
    else if (arr[mid] < target) low = mid + 1  // go right
    else high = mid - 1                        // go left
  }
  return -1  // not found
}

Watch the off-by-one bugs

Binary search is famous for tiny bugs in the boundaries. Two things to get right:

Use low <= high (not low < high) so you still check the final single item.
After checking mid, move past it: low = mid + 1 or high = mid - 1. If you forget the +1/-1, you can loop forever.

CAUTION

When unsure, test the one-item case in your head: if low === high, is there still an item to check? Yes — so the loop condition must be <=.

In one sentence

Binary search finds an item in a sorted list by repeatedly checking the middle and throwing away the half that can’t contain the target — turning a huge search into a handful of steps.

Want to go deeper?

Switch to Expert mode above for the recursive version, the overflow-safe midpoint, and clever “binary search on the answer” applications.