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 can be preferable for small arrays or a few searches through unsorted data. The crossover depends on the implementation, hardware and workload; include any sorting cost when comparing them.

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 + Math.floor((high - low) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

This form computes the midpoint without JavaScript bitwise coercion to 32 bits. The unsigned right shift operator truncates its numeric input to 32 bits, so it is not a general replacement for division on large indices.

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 with integer division when the bounds are nonnegative.
• 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.

Algorithm reference: NIST Dictionary of Algorithms and Data Structures: binary search. The interactive practice uses distinct integers so its search bounds and answers are unambiguous.