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

LeetCode 704 - Binary Search

Given a sorted array of integers and a target value, return the index of the target or -1 if not found.

func binarySearch(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2 // avoids overflow vs (lo+hi)/2
        if nums[mid] == target {
            return mid
        } else if 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.

Left and Right Boundaries

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

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

// Find leftmost (first) occurrence of target
func leftBound(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    result := -1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if nums[mid] >= target {
            if nums[mid] == target {
                result = mid
            }
            hi = mid - 1 // keep searching left
        } else {
            lo = mid + 1
        }
    }
    return result
}

// Find rightmost (last) occurrence of target
func rightBound(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    result := -1
    for lo <= hi {
        mid := lo + (hi-lo)/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.

func searchRange(nums []int, target int) []int {
    return []int{leftBound(nums, target), rightBound(nums, target)}
}

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?"

// Helper: find max element in a slice
func maxElement(a []int) int {
    m := a[0]
    for _, v := range a[1:] {
        if v > m { m = v }
    }
    return m
}

// Helper: sum all elements
func sum(a []int) int {
    s := 0
    for _, v := range a { s += v }
    return s
}

// Minimum capacity to ship packages within D days
func shipWithinDays(weights []int, days int) int {
    lo, hi := maxElement(weights), sum(weights)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if canShip(weights, mid, days) {
            hi = mid // mid works, try smaller
        } else {
            lo = mid + 1 // mid too small
        }
    }
    return lo
}

func canShip(weights []int, capacity, days int) bool {
    d, load := 1, 0
    for _, w := range weights {
        if load+w > capacity {
            d++
            load = 0
        }
        load += w
    }
    return d <= days
}

The insight: if capacity X works, then X+1 also works (monotonic). Binary search finds the smallest X that satisfies the condition.

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

Given a sorted array that has been rotated at an unknown pivot, search for a target value in O(log n) time.

func searchRotated(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if nums[mid] == target {
            return mid
        }
        if nums[lo] <= nums[mid] { // left half is sorted
            if target >= nums[lo] && target < nums[mid] {
                hi = mid - 1
            } else {
                lo = mid + 1
            }
        } else { // right half is sorted
            if target > nums[mid] && target <= nums[hi] {
                lo = mid + 1
            } else {
                hi = mid - 1
            }
        }
    }
    return -1
}

Common Bugs

Overflow: (lo + hi) / 2 overflows for large values. Use lo + (hi-lo)/2.
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.

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)
Use lo + (hi-lo)/2 to avoid integer overflow
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
Works on any monotonic function, not just sorted arrays
Common bugs: overflow, infinite loops from lo = mid, off-by-one on loop condition