Binary search introduction

Binary search

To find a value in a sorted array, you don't have to look at every element. Binary search repeatedly halves the search range, throwing away the half that can't contain the answer. That turns an O(n) scan into O(log n).

The mechanism

Keep two bounds, lo and hi, around the range that might contain the target. Look at the middle. If it's the target, done. If the target is larger, it must be in the right half, so move lo past the middle. If smaller, move hi before the middle. Repeat until the range is empty.

function binarySearch(nums, target):
    lo, hi = 0, length(nums) - 1
    while 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

Watch the details

Prerequisite: the data must be sorted (or otherwise monotonic in the property you're testing).
Mid: use lo + (hi-lo)/2, not (lo+hi)/2, to avoid overflow on large indices.
Boundaries: the classic loop uses lo <= hi with an inclusive hi. Off-by-one errors here are the #1 binary-search bug — be deliberate about whether hi is inclusive.

Beyond plain search

The real power is searching for a boundary: the leftmost index of a value, the insertion point, the smallest input that satisfies a condition. Any time a yes/no test flips from false to true as the input grows, binary search can find the flip in O(log n). The problems here build from plain lookup up to rotated arrays and grids.