Searching

Linear search checks items one by one: O(n), and it works on any list. Binary search needs a sorted list, but it is O(log n): look at the middle item, then throw away the half that cannot contain the target, and repeat. A million sorted items need at most about 20 checks.

How it reads

• low and high mark the part of the list that could still hold the target
• Each step discards half, so 200 items take at most 8 steps
• When low passes high, the target is not there

Cloud tip: Python's bisect module has binary search built in: bisect.bisect_left(items, target).