PART 4 · DSA AND COMPLEXITY · CHAPTER 23

Binary search, including search on the answer

FreeLesson 48 of 78

Cut the search space in half with every look. On sorted data, 10 lakh items need about 20 looks. The harder version searches for the answer itself.

THE ONE TEMPLATE TO MEMORISEPYTHON 3.12

import bisect

def lower_bound(xs, target):    # first i with xs[i] >= target
    lo, hi = 0, len(xs)
    while lo < hi:
        mid = (lo + hi) // 2
        if xs[mid] < target:
            lo = mid + 1                # answer is to the right
        else:
            hi = mid                    # mid could be the answer
    return lo

dates = ["2025-01-10", "2025-02-02", "2025-03-05", "2025-04-20"]
for d in ["2025-02-02", "2025-03-01", "2026-01-01"]:
    print(d, lower_bound(dates, d), bisect.bisect_left(dates, d))

Output

2025-02-02 1 1
2025-03-01 2 2
2026-01-01 4 4

BINARY SEARCH ON THE ANSWER: SLOWEST RATE THAT STILL MEETS THE DEADLINEPYTHON 3.12

import math

files_rows = [1_20_000, 45_000, 3_00_000, 80_000, 2_10_000]
HOURS = 8

def hours_needed(rate):                # files run one at a time
    return sum(math.ceil(rows / rate) for rows in files_rows)

def min_rate(hours):                   # binary search on the answer
    lo, hi = 1, max(files_rows)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_needed(mid) <= hours:
            hi = mid                   # fast enough: try slower
        else:
            lo = mid + 1               # too slow: go faster
    return lo

r = min_rate(HOURS)
print(r, "rows/hour ->", hours_needed(r), "hours")
print(r - 1, "rows/hour ->", hours_needed(r - 1), "hours")

Output

120000 rows/hour -> 8 hours
119999 rows/hour -> 9 hours

Same family: "Koko eating bananas", "ship packages within D days", "minimum batch size".

Use binary search when	Cost	Example
Data is sorted and you need a position	O(log n)	First order on or after a date
A yes/no check flips once as the answer grows	O(check x log range)	Minimum throughput, minimum capacity
You need many lookups on static sorted data	O(log n) each, no extra memory	Page 43 trade-off vs a set

DE FLAVOUR: WHICH DAY DID THE BAD DATA START?PYTHON 3.12

from datetime import date, timedelta

days = [date(2025, 3, 1) + timedelta(d) for d in range(60)]
checks = 0
def output_is_wrong(day):            # pretend: rerun and compare
    global checks
    checks += 1
    return day >= date(2025, 4, 7)   # the bug shipped on 7 April

lo, hi = 0, len(days)
while lo < hi:
    mid = (lo + hi) // 2
    if output_is_wrong(days[mid]):
        hi = mid
    else:
        lo = mid + 1
print("first bad day:", days[lo], "after", checks, "checks, not 60")

Output

first bad day: 2025-04-07 after 6 checks, not 60

Practice before you move on

Write a binary search that returns the first index of a target in a sorted list that has duplicates.
Use the search on the answer template to find the smallest daily capacity that clears a list of order sizes in three days.