Bifalgorithm post

Find one number in a sorted list of a billion in about 30 steps. That is binary search. The trick is that the array is sorted. So start by looking at the middle element. Target too big, throw away the left half. Too small, throw away the right. Either way, half the array is gone. Look at the new middle and have again and again. Closing in every step. A billion items collapses to just 30 checks because each step doubles your reach. That is log N. Halve. Compare, repeat. That is binary search.

Find one number in a sorted list of a billion in about 30 steps. That is binary search. The trick is that the array is sorted. So start by looking at the middl…