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
- loop invariant — A statement about a loop's variables that is true before the loop starts and stays true after every iteration.
- off-by-one error — A bug where a count or index is one too many or one too few, such as looping one step past the end.
- bisect module — Python's standard-library module of correct binary-search functions for sorted lists.
- monotone predicate — A yes-or-no test over ordered values that is False up to some point and True from then on, never switching back.
- logarithmic time — Work that grows by only one step each time the input doubles, written O(log n), typical of algorithms that halve the problem each step.
- git bisect — A command that finds the commit that introduced a bug by binary search: you mark commits good or bad and Git checks out the next one to test.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Binary Search And Its Invariant — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers
- Investigating History: blame, bisect And worktree — Advanced Git Internals & Distributed Workflows