Binary search
Finding a value in sorted data by checking the middle and discarding the half that can't contain it.
Definition
Each step compares the middle element with the target and keeps only the half where the target can be, so it needs about log2(n) steps: around 20 for a million elements. It works on any yes/no question that switches from no to yes exactly once, not only on arrays, which is called binary search on the answer. The usual bugs are ranges that don't shrink (infinite loops) and midpoints that overflow.
In practice
git bisect finds the commit that broke a build among 1,000 commits in about 10 test runs.
Learn it in context
Lessons that use this term.