Searching: from every item to twenty

Finding one item in a million. The difference between the two ways of doing it is the clearest illustration of complexity there is.

Linear search

for i, item in enumerate(items):
    if item == target:
        return i
return -1

Look at each until found. Works on anything, needs no order, O(n). On a million items, up to a million comparisons.

Binary search

Only on sorted data. Look at the middle, and throw away half:

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

Each step halves what is left. A million items:

1,000,000 -> 500,000 -> 250,000 -> ... -> 1

That is 20 steps, because 2²⁰ is about a million. O(log n).

A billion items in thirty steps.

The two bugs everyone writes

The infinite loop. lo = mid instead of lo = mid + 1. When lo and hi are adjacent, mid equals lo, and the range never shrinks.

The overflow. (lo + hi) / 2 overflows in C++ or Java when both are large. Write lo + (hi - lo) / 2. Python has arbitrary integers so it is safe there, and the habit is still worth having.