Lessons · Python · searching sorted data

Halve the search space every step

In a sorted sequence, look at the middle: the target is either there, to the left, or to the right. Throw away half each time.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

Every database index, git bisect, and 'find the version that broke it' works this way. A million items takes twenty looks instead of a million.

How to think about it

Is the middle too small or too big? Keep two edges, low and high. Compute the middle. If the middle is too small, move low past it; if too big, move high before it. Stop when they cross.

Worked example

pages = [3, 8, 15, 21, 42]

Sorted. Find 21.

lo, hi = 0, len(pages) - 1

Edges.

while lo <= hi:

While the range is non-empty.

    mid = (lo + hi) // 2

Middle position.

    if pages[mid] == 21: break

Found at position 3.

    elif pages[mid] < 21: lo = mid + 1

Too small: discard the left half.

    else: hi = mid - 1

Too big: discard the right half.

Your turn

Move the correct edge when the middle is too small.

if items[mid] < target:
     = mid + 1

The trap

Forgetting the +1 / -1 when moving an edge. The loop then never shrinks and runs forever.

Practise searching sorted data on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.