Pattern 4 of 27

Binary Search on Sorted Data

Halve a sorted range on every comparison to find a value, a boundary, or a turning point in logarithmic time.

Cost: O(log n) time, O(1) space
Problems: 6

When to reach for it

The array is sorted, or sorted and then rotated.
The prompt asks for O(log n).
You need the first or last position where a condition becomes true.

How it works

Binary search is less about finding a value and more about finding the boundary where a yes/no condition flips. Keep an invariant that the answer lies inside [lo, hi], look at the middle, and throw away the half that cannot contain it. Written as "first index where nums[i] is at least target", one loop covers exact search, insert position, and first and last occurrence. Rotated arrays still work because at least one half around the middle is always sorted normally.

The template

Written for Search Insert Position (write-up)

def search_insert(nums, target):
    lo, hi = 0, len(nums)             # the answer is always inside [lo, hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Open in the editor Trace it line by line

Six problems, in learning order

1.Search in Rotated Sorted ArrayLeetCode 33Work out which half is sorted, then check whether the target falls inside it.Medium
2.Find First and Last Position of Element in Sorted ArrayLeetCode 34Run the boundary search twice: first index at least target, first index above target.Not in the curated 370 yet.Medium
3.Search Insert PositionLeetCode 35The lower bound itself is the insert position.Easy
4.Find Minimum in Rotated Sorted ArrayLeetCode 153Compare the middle with the right end; the minimum sits where the order breaks.Medium
5.Find Peak ElementLeetCode 162Walk uphill: if the right neighbour is larger, a peak exists to the right.Medium
6.Binary SearchLeetCode 704Plain search for an exact value.Easy

What usually goes wrong

Mixing inclusive and exclusive bounds, which causes infinite loops or skipped elements.
A middle calculation that never moves lo when hi is exactly lo + 1.
In rotated arrays, comparing with the wrong end when deciding which half is sorted.