S032 · Binary Search — the Pattern Behind 100 Problems

"""bsearch_lab.py — three shapes of binary search, one file."""
from __future__ import annotations
import bisect
import math
from typing import Callable, List
 
# ---------- Template A · classic ----------
def binary_search(arr: List[int], target: int) -> int:
    """Return index of target, or -1. Space: [lo, hi]."""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2        # overflow-safe form
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1                 # target is strictly right
        else:
            hi = mid - 1                 # target is strictly left
    return -1
 
# ---------- Template B · lower bound ----------
def lower_bound(arr: List[int], target: int) -> int:
    """First index i where arr[i] >= target. == bisect_left. Space: [lo, hi)."""
    lo, hi = 0, len(arr)                 # note: hi = n, not n-1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1                 # predicate (>= target) still False
        else:
            hi = mid                     # predicate True, but earlier index may also be True
    return lo
 
def upper_bound(arr: List[int], target: int) -> int:
    """First index i where arr[i] > target. == bisect_right."""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
# ---------- Binary search on the answer ----------
def min_ship_capacity(weights: List[int], days: int) -> int:
    """Smallest capacity C such that all weights ship in <= days days, in order."""
    def feasible(cap: int) -> bool:
        d, load = 1, 0
        for w in weights:
            if load + w > cap:
                d += 1
                load = 0
            load += w
        return d <= days
 
    lo, hi = max(weights), sum(weights)  # search space
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid                     # try smaller
        else:
            lo = mid + 1                 # need bigger
    return lo
 
def bsearch_float(predicate: Callable[[float], bool],
                  lo: float, hi: float,
                  iterations: int = 100) -> float:
    """Fixed-iteration float binary search — safer than epsilon comparisons."""
    for _ in range(iterations):
        mid = (lo + hi) / 2
        if predicate(mid):
            hi = mid
        else:
            lo = mid
    return lo
 
def sqrt(n: float) -> float:
    """Compute sqrt via binary search on the answer."""
    return bsearch_float(lambda x: x * x >= n, 0.0, max(1.0, n))
 
# ---------- Demo ----------
if __name__ == "__main__":
    arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    print("classic search(23):    ", binary_search(arr, 23))     # 5
    print("classic search(24):    ", binary_search(arr, 24))     # -1
    print("lower_bound(24):       ", lower_bound(arr, 24))       # 6
    print("upper_bound(23):       ", upper_bound(arr, 23))       # 6
    print("bisect.bisect_left(24):", bisect.bisect_left(arr, 24))
 
    dupes = [1, 2, 2, 2, 3]
    print("count of 2 via bounds: ", upper_bound(dupes, 2) - lower_bound(dupes, 2))  # 3
 
    weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    print("min capacity (5 days): ", min_ship_capacity(weights, 5))   # 15
    print("min capacity (3 days): ", min_ship_capacity(weights, 3))   # 20+
 
    print(f"sqrt(2) ≈ {sqrt(2):.10f}  vs math.sqrt = {math.sqrt(2):.10f}")