Engineering Notes

Binary Search

3 min read

Binary Search

Binary search finds a target in a sorted array by repeatedly halving the search space. It runs in O(log n) time — searching 1 billion elements takes at most 30 comparisons.

Why It Matters

Binary search is one of the most important algorithms in CS. It’s used in database indexes, searching sorted files, finding boundaries, and as a general problem-solving technique (binary search on the answer).

The Algorithm

1. Set lo = 0, hi = len(arr) - 1
2. While lo <= hi:
   a. mid = (lo + hi) // 2
   b. If arr[mid] == target: found
   c. If arr[mid] < target: lo = mid + 1
   d. If arr[mid] > target: hi = mid - 1
3. Not found

Code Example

def binary_search(arr: list, target) -> int:
    """Return index of target, or -1 if not found."""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
 
assert binary_search([1, 3, 5, 7, 9, 11], 7) == 3
assert binary_search([1, 3, 5, 7, 9, 11], 4) == -1
 
# Find leftmost insertion point (like bisect_left)
def bisect_left(arr: list, target) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
# Find first element >= target
assert bisect_left([1, 3, 5, 5, 5, 7], 5) == 2  # first 5 is at index 2
assert bisect_left([1, 3, 5, 5, 5, 7], 4) == 2  # 4 would insert at index 2
 
# Binary search on the answer
# Example: find the square root of n (integer)
def int_sqrt(n: int) -> int:
    lo, hi = 0, n
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid == n:
            return mid
        elif mid * mid < n:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi  # largest integer whose square <= n
 
assert int_sqrt(16) == 4
assert int_sqrt(20) == 4  # floor(sqrt(20)) = 4

Python’s bisect Module

import bisect
 
arr = [1, 3, 5, 7, 9]
bisect.bisect_left(arr, 5)   # 2 — insertion point before existing 5
bisect.bisect_right(arr, 5)  # 3 — insertion point after existing 5
bisect.insort(arr, 4)        # arr is now [1, 3, 4, 5, 7, 9]
  • Searching in sorted arrays
  • Finding boundaries (first/last occurrence)
  • “Binary search on the answer” — when the answer is monotonic (if X works, X+1 also works)
  • Minimizing/maximizing a value subject to a condition

Common Mistakes

  1. Off-by-one errors — lo <= hi vs lo < hi depends on the variant
  2. Integer overflow — use mid = lo + (hi - lo) // 2 in languages with fixed-size ints
  3. Forgetting the input must be sorted

Graph View

Backlinks