Binary search
When a list is already sorted, you never need to scan it from front to back.
Binary search looks at the middle element, and because the list is sorted it
learns which half the target must be in - so it throws the other half away.
Repeat that on the half that is left and the search range shrinks by half every
step, finding any value in a million-item list in about twenty comparisons.
Keep two bounds, lo and hi, that mark the part of the list still worth
checking. Compare the middle value to the target: equal means you found it,
too small means the answer is to the right (move lo up), too big means it is
to the left (move hi down). When lo passes hi, the range is empty and the
value is not there.
Your task: write binary_search(items, target), where items is a list
sorted in ascending order. Return the index of target, or -1 if it is not
in the list.
You'll practice:
- Narrowing a search range with two moving bounds
- Handling the not-found and empty-list cases cleanly