Binary Search

Find the position of a value in a sorted array, or report that it isn't there, in logarithmic time.

nums = [-4, 1, 3, 8, 12, 19, 24, 30, 41], target = 24step 1/5

lo↓

hi↓

-4

Searching for 24. If it exists at all, it's somewhere in this range.

1def search(nums, target):
2    lo, hi = 0, len(nums) - 1
3    while lo <= hi:
4        mid = lo + (hi - lo) // 2
5        if nums[mid] == target:
6            return mid
7        if nums[mid] < target:
8            lo = mid + 1
9        else:
10            hi = mid - 1
11    return -1

Read the 5 steps as text

1Searching for 24. If it exists at all, it's somewhere in this range.
2Middle of the range is index 4, holding 12.
312 < 24, and everything to its left is smaller still. Discard 5 entries.
4Middle of the range is index 6, holding 24.
524 is the target. Found at index 6.

The idea

Sortedness is information, and a linear scan throws all of it away. If you check the middle element and it's too small, then it and everything to its left are too small — you've ruled out half the array with a single comparison.

Repeat and the search space halves every time: 1000 elements becomes 500, then 250, then 125. Twenty comparisons is enough for a million entries. That's the whole pattern, and it's why the phrase "the array is sorted" in a problem statement is never decoration.

The part that trips people up isn't the idea, it's the bookkeeping. Every binary search is a promise: "if the answer exists, it is inside [lo, hi]". Every line you write has to keep that promise true.

The approach

1Track the closed range [lo, hi] that could still contain the answer, starting as the whole array.
2Look at the middle. If it's the target, you're done.
3If it's too small, the answer must be strictly to the right, so lo = mid + 1.
4If it's too big, the answer must be strictly to the left, so hi = mid − 1.
5When lo passes hi the range is empty and the value isn't present.

Complexity

Time

O(log n)

Space

O(1)

Each iteration discards half of what remains, so the loop runs about log₂(n) times.

Code

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

What goes wrong

•Writing `lo = mid` instead of `lo = mid + 1`. If mid is already ruled out and you keep it in the range, a two-element range stops shrinking and the loop spins forever.
•Using `while (lo < hi)` with a closed range. The final single-element range never gets checked, so the target sitting at that index is reported as missing.
•Computing `(lo + hi) / 2` in a fixed-width integer type. On large arrays that sum overflows; `lo + (hi - lo) / 2` is the same number and cannot.
•Reaching for binary search on unsorted data. It won't be slow, it'll be wrong — and it will still return an answer, which is worse.