binary search

Finding a target in sorted data by comparing it with the middle item and throwing away the half where it cannot be.

In more detail

Each step halves the remaining range, so a million items need about twenty comparisons, O(log n). It only works on sorted data, and it is easy to get the boundaries wrong. The same halving idea finds the first point where a yes-or-no test switches from no to yes, which is how git bisect finds the commit that introduced a bug.

Example

git bisect uses binary search over history, which is ordered from good to bad.

Related terms

Taught in

References