Code Gym

You don't stop lifting weights just because you own a car jack.

← All topics

Binary Search

Any time the search space is monotonic -- sorted array, or 'if X works then everything bigger/smaller also works' -- you can throw away half the remaining space each step instead of scanning linearly. O(log n) instead of O(n).

Easy reps

704. Binary Search

Given a sorted array of distinct integers and a target, return its index, or -1 if it isn't present.

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

The textbook version. Compare the midpoint to the target, discard the half that can't contain it, repeat. The loop invariant -- the answer, if it exists, is always within [lo, hi] -- is the thing worth internalizing here.

35. Search Insert Position

Given a sorted array of distinct integers and a target, return the index if found, or the index it would be inserted at to keep the array sorted.

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

This is the 'find the first position satisfying a condition' variant: instead of stopping on an exact match, lo converges on the first index where nums[i] >= target, which is exactly the insert point.

Level up

Same topic, no training wheels. Solve these on your own before you check the editorial.