binary search

Articles

SRT Algorithm Binary search Finds the “no → yes” boundary in ordered data in log₂ n checks. O(log n) 2 problems SRT Technique Binary search on the answer If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving. O(log D · cost of a check) 2 problems SRT Algorithm Exponential search Steps 1, 2, 4, 8, … until you overshoot, then binary search: when the bound is unknown or the answer is near. 2⌊log₂ i⌋ + 1 questions to position i 1 problem SRT Algorithm Interpolation search Estimate the place from the values at the edges: log log n probes on uniform keys and up to n on awkward ones. ≈ log₂ log₂ n on average, n in the worst case 1 problem DP Technique Digit DP Lucky tickets in any range in one pass over the digits: 55,252 out of a million, and any range up to 10¹⁸, in about a millisecond. O(D · 10 · S) 2 problems NUM~ Algorithm Bisection and Newton's method A root of an equation: halving an interval is reliable, Newton's tangents are fast. bisection: log₂((b − a)/ε) steps; Newton: about log₂ of the number of digits 2 problems SYS Data structure Inverted index and BM25 A dictionary “word → documents that contain it”: a query reads a few short lists instead of all the texts. O(total length of the query words' lists); AND by galloping O(m·log(n/m)) 2 problems TEC Technique Coordinate compression Replace values up to a billion by their ranks in order, and build arrays and trees over the ranks. O(n log n) to compress 2 problems

Problems

Earthquakes in a range A compressed list of positions A new server on the ring A novel in k days A stop on the way Bike stations How a Python list grows The k-th root What an instalment plan costs In the same sentence The density threshold Nobody rides far

Often together

interviews 6 searching 5 classic 5 contests 3 array 2 compression 2 search engines 2 databases 2 version control 1 greedy 1 optimization 1 measurement 1