2 releases
0.1.1 | Oct 24, 2020 |
---|---|
0.1.0 | Oct 24, 2020 |
#1872 in Algorithms
Used in robust-git-bisect
105KB
2.5K
SLoC
Robust Binary Search
Robust Binary Search provides a binary search implementation which is robust against errors during the search. In other words, if the comparison function sometimes returns an incorrect result, the search in this project will still converge on the correct solution.
This is adapted from the multiplicative weights algorithm in "Noisy binary search and its applications" by Karp and Kleinberg, with adjustments to make it deterministic and then extended to support directed acyclic graphs.
Usage
See AutoSearcher
for binary search over a linear range and AutoCompressedDAGSearcher
for binary
search over a graph.
If you're looking for a git bisect replacement, see the robust-git-bisect
crate which uses this
library.
Performance
This code is optimized to minimize the number of tests executed (i.e. number of iterations) and not necessrily the CPU time of the search algorithm itself, so this will be slower than a plain binary search if the test is deterministic.
The linear algorithm (Searcher
and AutoSearcher
) takes approximately O(log N)
time per
iteration. The graph algorithm (CompressedDAGSearcher
and AutoCompressedDAGSearcher
) takes
approximately O(segments)
time per iteration.
Dependencies
~3–11MB
~103K SLoC