Binary Search

How binary search works

Imagine looking up a word in a printed dictionary. You don't start from page 1 — you flip to roughly the middle. If the word you want comes earlier alphabetically, you ignore the back half and repeat with the front half. Binary search does the same thing, on a sorted array, in code.

The algorithm tracks two indices, low and high, marking the boundaries of the range that could still contain the target. On each iteration:

1. Compute the midpoint: mid = floor((low + high) / 2).
2. Compare arr[mid] to the target.
3. If equal, return mid — found.
4. If arr[mid] is smaller, the target must be to the right; set low = mid + 1.
5. If arr[mid] is larger, set high = mid - 1.
6. Repeat until found, or until low > high (target absent).

The halving step is the magic. With a million-item array, the range halves to 500,000 → 250,000 → 125,000 → ... → 1 in just 20 comparisons. Linear search would average 500,000.

When to use binary search

• Your data is sorted, or you can afford to sort it once and search many times.
• You need an exact match, or the leftmost or rightmost match.
• Random-access reads are cheap (an array, not a linked list).
• You want predictable worst-case performance — binary search has no pathological inputs.

If your data changes constantly, the cost of keeping it sorted may outweigh the search savings. A hash table gives O(1) average lookups for unordered point queries. A balanced binary search tree gives O(log n) lookups and cheap ordered traversal.

Binary search vs linear search

	Linear search	Binary search
Time complexity (worst)	O(n)	O(log n)
Requires sorted input	No	Yes
1,000,000 items (worst case)	1,000,000 comparisons	20 comparisons
Best for	Tiny or unsorted arrays	Sorted arrays, repeated queries

Linear search beats binary search only when the array is small (under roughly 30 elements, where the log-factor advantage is dwarfed by control overhead) or when the cost of sorting once exceeds the savings across all future queries.

Pseudo-code

function binarySearch(arr, target):
    low = 0
    high = arr.length - 1
    while low <= high:
        mid = floor((low + high) / 2)
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1   # not found

JavaScript implementation

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = (low + high) >>> 1;  // unsigned shift = safe integer divide
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

The (low + high) >>> 1 trick avoids integer overflow on huge arrays — the same bug that lived in Java's standard library for nearly a decade before being fixed in 2006.

Python implementation

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Python's standard library also offers bisect.bisect_left and bisect.bisect_right — implementations of the leftmost/rightmost variants that you should use in production rather than rolling your own.

Common bugs and edge cases

• Off-by-one in the loop condition. Use low <= high, not low < high — the latter misses the case where low and high converge on the target index.
• Integer overflow on (low + high). In languages with fixed-width integers, prefer low + (high - low) / 2 or an unsigned shift.
• Forgetting to update boundaries. Always set low = mid + 1 or high = mid - 1, not mid, or the loop spins forever.
• Searching unsorted data. The algorithm returns garbage silently — there's no runtime check.