What is binary search?
A way to find an item in a sorted list by cutting the search area in half with every step.
Someone picks a number from one to a thousand, and after each guess says higher or lower. With the right strategy, you never need more than ten guesses.
What it is
That strategy is binary search: a way to find an item in a sorted list by cutting the search area in half with every step.
How it works
Look at the middle item. If it's the one you want, you're done. If your target is smaller, throw away the right half. If it's bigger, throw away the left half. Repeat on what's left. Each step halves the list, so a million items take about twenty steps, and a billion about thirty.
Why it matters
In Big O terms, that's O(log n). The catch: the data has to be sorted first. Git's bisect command uses the same trick to find the commit that broke your code.
