Binary Search

Binary search works on sorted arrays. Each step eliminates half the remaining search space — that's what gives O(log n).

The tricky part isn't the algorithm — it's the boundary conditions. Off-by-one errors are extremely common. Use this template consistently:

Classic template: left=0, right=len-1, while left <= right, mid = left + (right-left)//2

The real power: binary search isn't just for finding exact values. It applies whenever:
• You can define a monotonic condition (true/false boundary)
• You're searching for a minimum/maximum that satisfies a condition
• "Find the first/last position of X"
• "Minimum capacity to ship in D days"
• "Koko eating bananas"

When you see: "find minimum X such that condition(X) is true" → think binary search on the answer, not the array.

1import bisect
2
3# ── Classic binary search ─────────────────────────────────────────
4def binary_search(nums: list[int], target: int) -> int:
5    left, right = 0, len(nums) - 1
6    while left <= right:
7        mid = left + (right - left) // 2   # avoids integer overflow
8        if nums[mid] == target:
9            return mid
10        elif nums[mid] < target:
11            left = mid + 1
12        else:
13            right = mid - 1
14    return -1
15
16# ── First and Last Position ───────────────────────────────────────
17def search_range(nums: list[int], target: int) -> list[int]:
18    def find_left():
19        left, right, pos = 0, len(nums)-1, -1
20        while left <= right:
21            mid = left + (right - left) // 2
22            if nums[mid] == target: pos = mid; right = mid - 1
23            elif nums[mid] < target: left = mid + 1
24            else: right = mid - 1
25        return pos
26
27    def find_right():
28        left, right, pos = 0, len(nums)-1, -1
29        while left <= right:
30            mid = left + (right - left) // 2
31            if nums[mid] == target: pos = mid; left = mid + 1
32            elif nums[mid] < target: left = mid + 1
33            else: right = mid - 1
34        return pos
35
36    return [find_left(), find_right()]
37
38# ── Koko Eating Bananas (binary search on answer) ─────────────────
39import math
40def min_eating_speed(piles: list[int], h: int) -> int:
41    def can_finish(speed: int) -> bool:
42        return sum(math.ceil(p / speed) for p in piles) <= h
43
44    left, right = 1, max(piles)
45    while left < right:
46        mid = left + (right - left) // 2
47        if can_finish(mid):
48            right = mid       # try smaller speed
49        else:
50            left = mid + 1    # need faster speed
51    return left
52
53# ── Search in Rotated Sorted Array ───────────────────────────────
54def search_rotated(nums: list[int], target: int) -> int:
55    left, right = 0, len(nums) - 1
56    while left <= right:
57        mid = left + (right - left) // 2
58        if nums[mid] == target: return mid
59        if nums[left] <= nums[mid]:            # left half is sorted
60            if nums[left] <= target < nums[mid]: right = mid - 1
61            else: left = mid + 1
62        else:                                  # right half is sorted
63            if nums[mid] < target <= nums[right]: left = mid + 1
64            else: right = mid - 1
65    return -1
66
67# ── Python bisect (built-in binary search) ────────────────────────
68arr = [1, 3, 5, 7, 9]
69print(bisect.bisect_left(arr, 5))    # 2 — leftmost position for 5
70print(bisect.bisect_right(arr, 5))   # 3 — rightmost position for 5
71
72print(binary_search([1,3,5,7,9,11,13], 7))   # 3
73print(search_range([5,7,7,8,8,10], 8))        # [3, 4]
74print(min_eating_speed([3,6,7,11], 8))        # 4