11. Binary Search

What you'll learn

• 1Hand-code binary search avoiding off-by-one errors
• 2Use bisect_left and bisect_right correctly
• 3Distinguish exact-match, lower-bound, and upper-bound queries

Overview

Binary search divides the search space in half each step — O(log n). It only works on a sorted (or monotone) sequence. Edge cases (off-by-one, infinite loops) are the main source of bugs.

Core Concepts

1. Find exact match

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

2. Lower bound (first index >= target)

def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo   # may be len(a) if all < target

3. Upper bound (first index > target)

def upper_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

4. The bisect module

import bisect
a = [1, 3, 5, 5, 5, 7, 9]

bisect.bisect_left(a, 5)    # 2 (first index of 5)
bisect.bisect_right(a, 5)   # 5 (first index > 5)
bisect.bisect_right(a, 5) - bisect.bisect_left(a, 5)   # count of 5s

bisect.insort(a, 4)         # insert 4 in sorted order

Examples

Example 1 — src/01_binary_search.py

Iterative and recursive binary search.

Example 2 — src/02_lower_upper.py

lower_bound and upper_bound by hand.

Example 3 — src/03_bisect_demo.py

bisect_left, bisect_right, insort.

Example 4 — src/04_search_2d.py

Search a row-and-column-sorted matrix.

Common Mistakes

1. Forgetting hi = len(a) - 1 vs hi = len(a) inconsistency. Pick one convention and stick to it.
2. (lo + hi) // 2 overflows in some languages — in Python it's fine, but be aware.
3. Updating lo = mid (not mid+1) → infinite loop when range = 2.
4. Searching an unsorted array. Sort first or use a hash.

Recap

• Pre-condition: sorted (or monotone) input.
• bisect_left / bisect_right cover most needs.
• Off-by-one bugs are common — test on boundary inputs.

Try It

1. BOJ 1920 (Find a number).
2. BOJ 10816 (Sorted card 2) — count occurrences.