Lesson 4 — Binary search

Binary search: halve the problem each step

If a list is sorted, you can do much better than checking every item. Look at the middle item: if it is too small, the target must be in the right half; if too big, in the left half. Throw away the wrong half and repeat. lo and hi mark the part of the list still in play.

mid = (lo + hi) // 2   # // divides and drops the decimals

Each step halves the list, so 1,000,000 items need only about 20 steps. This is O(log n).

Why it matters: databases, dictionaries and "guess the number" games all use this idea.