09. Binary Search

📋 Jump to Takeaways

Binary search eliminates half the search space with each comparison. It's the reason sorted arrays give O(log n) lookup instead of O(n). But binary search is more than "find a number in a sorted array" — it's a general technique for any problem where you can answer "is this value too high or too low?"

The Basic Template

def binary_search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2  # no overflow in Python; in Go/Java use: lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1  # not found

O(log n) time, O(1) space. Each iteration halves the search space.

Note: Python integers have arbitrary precision — no overflow risk with (lo + hi) // 2. This is a difference from languages like Go, C++, or Java where you'd use lo + (hi - lo) // 2.

Left and Right Boundaries

Often you don't just want "is it there?" — you want "where does it start?" or "where does it end?"

def left_bound(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    result = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] >= target:
            if nums[mid] == target:
                result = mid
            hi = mid - 1  # keep searching left
        else:
            lo = mid + 1
    return result

def right_bound(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    result = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] <= target:
            if nums[mid] == target:
                result = mid
            lo = mid + 1  # keep searching right
        else:
            hi = mid - 1
    return result

The key difference: when you find the target, don't return immediately — keep searching in one direction to find the boundary.

The `bisect` Module

Python's standard library includes bisect — a C-implemented binary search module that handles boundary searches for you.

import bisect

nums = [1, 3, 3, 3, 5, 7]

# bisect_left: index where target would be inserted (leftmost position)
bisect.bisect_left(nums, 3)   # 1 — first occurrence of 3

# bisect_right: index after the last occurrence
bisect.bisect_right(nums, 3)  # 4 — one past last occurrence of 3

# Count occurrences of 3:
bisect.bisect_right(nums, 3) - bisect.bisect_left(nums, 3)  # 3

# insort: insert while maintaining sorted order
bisect.insort(nums, 4)  # nums = [1, 3, 3, 3, 4, 5, 7]

bisect_left(a, x) — returns the leftmost index where x can be inserted to keep a sorted. If x exists, returns the index of the first occurrence.

bisect_right(a, x) — returns the rightmost insertion point. If x exists, returns one past the last occurrence.

insort(a, x) — inserts x into a in sorted position. O(n) because of the list shift, but the search is O(log n).

Using `bisect` for exact search

import bisect

def bisect_search(nums: list[int], target: int) -> int:
    i = bisect.bisect_left(nums, target)
    if i < len(nums) and nums[i] == target:
        return i
    return -1

LeetCode 34 - Find First and Last Position of Element in Sorted Array

import bisect

def searchRange(nums: list[int], target: int) -> list[int]:
    left = bisect.bisect_left(nums, target)
    right = bisect.bisect_right(nums, target)
    if left < len(nums) and nums[left] == target:
        return [left, right - 1]
    return [-1, -1]

Search on Answer (Binary Search on Result)

The most powerful application: when the answer itself is monotonic. Instead of searching an array, you search a range of possible answers.

Pattern: "What's the minimum/maximum value X such that condition(X) is true?"

LeetCode 875 - Koko Eating Bananas

import math

def minEatingSpeed(piles: list[int], h: int) -> int:
    def can_finish(speed: int) -> bool:
        return sum(math.ceil(p / speed) for p in piles) <= h

    lo, hi = 1, max(piles)
    res = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_finish(mid):
            res = mid         # mid works, save it
            hi = mid - 1      # try smaller
        else:
            lo = mid + 1      # mid too slow
    return res

The insight: if speed X finishes in time, then X+1 also finishes (monotonic). Binary search finds the smallest X that satisfies the condition.

LeetCode 1011 - Capacity To Ship Packages Within D Days

def shipWithinDays(weights: list[int], days: int) -> int:
    def can_ship(capacity: int) -> bool:
        d, load = 1, 0
        for w in weights:
            if load + w > capacity:
                d += 1
                load = 0
            load += w
        return d <= days

    lo, hi = max(weights), sum(weights)
    res = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_ship(mid):
            res = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return res

When Binary Search Applies

Binary search works when:

The search space is sorted or monotonic (if X works, everything beyond X also works)
You can check a candidate in O(n) or less
You can define clear boundaries (lo and hi)

Common "search on answer" problems:

Minimum speed to eat bananas in H hours
Split array into K subarrays minimizing the largest sum
Minimum capacity to ship within D days
Find the smallest divisor given a threshold

Rotated Sorted Array

A sorted array rotated at some pivot. Binary search still works — one half is always sorted.

LeetCode 33 - Search in Rotated Sorted Array

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid

        # Step 1: figure out which half is sorted
        if nums[lo] <= nums[mid]:  # left half [lo..mid] is sorted
            # Step 2: is target within the sorted left half?
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1       # yes → search left
            else:
                lo = mid + 1       # no → must be in the other (unsorted) half
        else:                       # right half [mid..hi] is sorted
            # Step 2: is target within the sorted right half?
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1       # yes → search right
            else:
                hi = mid - 1       # no → must be in the other (unsorted) half
    return -1

Common Bugs

Infinite loop: lo = mid instead of lo = mid + 1 when hi - lo == 1.
Off-by-one: lo <= hi vs lo < hi — depends on whether you're searching for exact match or boundary.
Wrong half: flipping the comparison direction.
Forgetting edge cases: empty array, single element, target at boundaries.

Note: Python doesn't suffer from integer overflow, so (lo + hi) // 2 is always safe. One less bug to worry about.

Practice Problems

Problem	Difficulty	Link
Binary Search	Easy	LeetCode 704
First Bad Version	Easy	LeetCode 278
Search Insert Position	Easy	LeetCode 35
Find First and Last Position	Medium	LeetCode 34
Search in Rotated Sorted Array	Medium	LeetCode 33
Find Minimum in Rotated Sorted Array	Medium	LeetCode 153
Koko Eating Bananas	Medium	LeetCode 875
Capacity To Ship Packages	Medium	LeetCode 1011

Key Takeaways

Binary search halves the search space each step — O(log n)
Python's bisect module gives you production-ready binary search: bisect_left, bisect_right, insort
No integer overflow in Python — (lo + hi) // 2 is always safe
Left/right boundary: when you find target, keep searching in one direction
"Search on answer" is the most powerful pattern — binary search over possible results when the condition is monotonic
bisect_left finds the first occurrence; bisect_right finds one past the last occurrence
Works on any monotonic function, not just sorted arrays