Exponential search

Ordinary binary search starts with the question “where is the middle?”, and for that you need to know where the end is. But the end is not always known. A page has broken, and all that is known is that it is broken in the latest version; nobody remembers a good one. A log keeps growing, and nobody knows its length. Below is the real history of this site, 904 commits, and the question “when did this part of the site appear?”. The search goes back from the latest commit in steps of 1, 2, 4, 8, … until it finds a commit where this part does not exist yet, and only then halves.

The algorithms catalogue appeared in the third commit from the end, and the search back finds that place in 4 checks, while git bisect over the whole history takes 10. But the maths textbook appeared 420 commits back, and there the search back needs 18 checks against 10. The cost of such a search depends not on the length of the history but on how far away the answer is. If the answer is near, it pays off; if the bound is unknown altogether, it is the only way.

The idea

Exponential search has two phases. First the steps double: check positions 1, 2, 4, 8, … until the answer is behind. Now the target lies between the last check and the one before it, on the stretch from 2^k−1 to 2^k, and ordinary binary search finds it. Both phases take about log₂ i steps, where i is the position of the answer, and the length of the data plays no part anywhere.

It is also called doubling search and galloping. Galloping is the same technique when the search must start not from the beginning but from where it stopped last time: this is how Timsort merges runs and how a search index intersects lists of occurrences. Both cases are taken apart in the articles on Timsort and the inverted index. Here it is the search itself and how many questions it needs.

How many questions

Let us state the problem in its pure form. An integer x ≥ 1 is hidden, there is no upper bound, and one may ask only about comparing x with a number. Doubling asks “x < 2?”, “x < 4?”, “x < 8?”, … until it hears “yes”, and then finds out the remaining binary digits of x one at a time, asking “x ≥ t?” for the middle of the remaining stretch.

Write down the answers: “yes” as 1, “no” as 0. First m zeros and a one, then the m low digits of x. This is x in binary, preceded by as many zeros as x has digits after the first. This notation was devised by Peter Elias in 1975, who called it the γ code. The answers of the search are the code of the number. Try it yourself: hide a number, and the scene shows the questions and the string of answers.

The second row in the scene is the improvement by Jon Bentley and Andrew Yao. Doubling spends half its questions finding out how many digits x has, and that number m + 1 can itself be found by the same doubling, faster. Bentley and Yao do exactly that: first they find the number of digits by doubling search, asking “x < 2^2j−1?” and then “x ≥ 2^t−1?”, and then find out the digits of x itself. The answers add up to the δ code of the same Elias, and the questions come to ⌊log₂ x⌋ + 2⌊log₂(⌊log₂ x⌋ + 1)⌋ + 1: for 10¹⁸, 70 instead of 119. The idea can be repeated further, the number of digits of the number of digits, and each level takes off a little more.

How many are really needed

Binary search on a known stretch of length N spends log₂ N questions, and fewer is impossible. Without a bound, can one manage with log₂ x questions and a small addition? No, and this is seen precisely through codes.

Any way of asking comparison questions without a bound that always finds x gives each x its own string of answers. These strings form a prefix code: if the string for x is the beginning of the string for y, then after these answers the search would stop with the answer x, although it could have been y.

Suppose some search spends at most log₂ x + c questions on x. Then 2^−ℓ_x ≥ 2^−c/x, and the sum Σ 1/x is infinite: Kraft's inequality is violated. So there is no such search. The same argument rules out log₂ x + log₂ log₂ x + c: the sum Σ 1/(x log₂ x) is also infinite. Its piece from 2^k to 2^k+1 holds 2^k terms each at least 1/(2^k+1(k + 1)), that is, at least 1/(2(k + 1)) in all, and the sum of such pieces is half the harmonic series. But Σ 1/(x (log₂ x)²) is finite, and the δ code with its two logarithms of the logarithm fits into the inequality with room to spare. The border between possible and impossible runs through which series converge.

Code

The listing does both jobs. The search back from the latest commit is compared with git bisect over the whole history. Then hidden numbers are guessed by doubling and by the Bentley–Yao method, and the strings of answers are checked against the γ and δ codes: the program verifies that they coincide character for character.

part of the site               first  back from HEAD  bisect all
the maths textbook               483              18          10
the Computer Science course      674              16          10
the Rubik's cube tutorial        415              18          10
the black hole visualisation     652              16          10
this algorithms catalog          901               4          10

            hidden x  doubling  Bentley-Yao  floor log2 x
                   1         1            1             0
                   2         3            4             1
                   5         5            5             2
                 100        13           11             6
             1000000        39           28            19
       1000000000000        79           50            39
 1000000000000000000       119           70            59

For small numbers the Bentley–Yao method sometimes even loses: for 2 it needs 4 questions against 3. The gain begins with numbers in the hundreds and grows: at 10¹⁸ it is 70 questions against 119, with 60 digits in the number itself.

What it costs

Doubling pays off over binary search on the whole stretch when the answer is closer than about √N from the start: 2 log₂ i < log₂ N exactly when i < √N. On a history of 904 commits that is the first thirty or so commits from the end. The search needs no memory, and each check touches the data once, which matters when a check is expensive: building a version, downloading a page, reading a block from disk.

Where it is used

• Finding the version that broke things. If a good version is unknown, steps back 1, 2, 4, … from the broken one find it, and then ordinary git bisect takes over. If the breakage is recent, this is also faster.
• Galloping. Merging runs in Timsort and intersecting lists of occurrences in a search index look for the next element not from the start but from the previous one, and pay the logarithm of the distance, not of the whole list.
• Binary search on the answer with no bound. When it is unknown how large the answer may be, its upper bound is found by doubling, and then it is searched for by binary search on the answer.
• Measurements. timeit.Timer.autorange in Python chooses the number of repetitions: it tries 1, 2, 5, 10, 20, 50, … until a measurement takes at least 0.2 seconds. Likewise empirical complexity is measured on sizes that double.
• Compression. Elias γ and δ codes, those very strings of answers, compress the gaps between numbers in search indexes: small numbers get short codes, large ones longer, and no separators are needed. This is the problem of the article.

History

In 1975 Peter Elias, in a paper on “universal” codes for the integers, built the γ and δ codes and showed that their length is nearly the smallest possible. A year later Jon Bentley and Andrew Yao, in the note “An almost optimal algorithm for unbounded searching”, looked at the same problem as a search: they described doubling, their improved method and an infinite ladder of further improvements, and proved that one can hardly do better in principle. The link between search and prefix codes behind this lower bound is an example of information theory answering questions about comparisons.

Problems

In the problem a list of occurrences of a word in “War and Peace” is compressed with δ codes, the strings of answers of the Bentley–Yao search, and it has to be decoded, reading the codes without separators.