02 — Binary Search & Monotonic Predicates

At a glance

After completing this lesson you can:

• Implement off-by-one bug-free binary search using lower and upper bounds (bisect_left vs bisect_right).
• Apply "binary search on answer" to monotonic feasibility predicates across search spaces.
• Quickly search multi-gigabyte timestamp-ordered log files in $O(\log n)$ disk page reads.

Time: ~50 minutes · Prerequisites: 01 — Two Pointers & Sliding Windows

Reading Companion

• Book: Grokking Algorithms (2nd Edition) — Aditya Y. Bhargava
• Chapter 1: Binary Search (The search problem, Logarithmic time).

Why this matters in production

Database B-Tree indexes, Kafka partition offsets, and timestamped log indexes all rely on binary search. When querying a time range in a 50 GB log file, scanning from line 1 takes minutes ($O(n)$). Because log entries are strictly monotonic in time, binary searching file byte offsets locates the exact starting minute in ~25 seeks ($O(\log n)$), returning metrics instantly.

Deep dive

1. The Monotonicity Condition

Binary search works on ANY problem with a monotonic predicate $P(x)$:

x:    1   2   3   4   5   6   7   8
P(x): F   F   F   F   T   T   T   T
                      ^
          First True (Transition Point)

2. Standard Binary Search Boundaries (Template)

To avoid infinite loops and boundary bugs:

def binary_search_first_true(low: int, high: int, predicate) -> int:
    while low < high:
        mid = (low + high) // 2
        if predicate(mid):
            high = mid      # Answer could be mid or to the left
        else:
            low = mid + 1   # Mid is definitely False, move right
    return low

Hands on

python3 phase1-cs-and-architecture/02-algorithmic-patterns/02-binary-search-and-intervals/examples/01_demo.py
python3 phase1-cs-and-architecture/02-algorithmic-patterns/02-binary-search-and-intervals/examples/02_trap.py

AI Trap & Code Review

# BAD AI-GENERATED CODE — INTEGER OVERFLOW / INFINITE LOOP ON MID
def binary_search_buggy(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid       # Bug: Infinite loop when high - low == 1!
        else:
            high = mid
    return -1

Exercises

1. Rung 1 (find_first_ge): Implement lower bound (bisect_left) returning the first index where arr[i] >= target in sorted array arr.
2. Rung 2 (search_timestamp_range — Fix the AI Bug): Fix an off-by-one error in a log range filter returning start and end indices for [start_ts, end_ts].
3. Rung 3 (binary_search_square_root): Compute integer square root of $n \ge 0$ in $O(\log n)$ without using floating point or math.sqrt.
4. Rung 4 (capacity_to_ship_packages): Given package weights and $D$ delivery days, find the minimum conveyor capacity needed to deliver within $D$ days using binary search on answer.
5. Rung 5 (find_peak_in_mountain): Find peak element index in a strictly increasing then strictly decreasing mountain array in $O(\log n)$ time.

Wrapping up

Can you explain?

1. Why must low or high strictly advance in binary search to prevent infinite loops?
2. What is the difference between bisect_left and bisect_right on duplicate values?
3. How does "binary search on answer" work when the underlying dataset is not sorted?

Further Reading & References

• CPython Source: listobject.c (Dynamic Array Implementation)
• Raymond Hettinger: Modern Dictionaries by Key-Sharing
• Alex Xu: System Design Interview — Rate Limiter Design
• Tim Roughgarden: Algorithms Illuminated Series