aldus.nexus

Binary search

Find one particle among 10^80 in about 266 yes or no questions, zooming from the cosmos to a single atom. Then think of a number and watch the same halving find it, or try to find mine.

address

think of a number

    numbers left per question

    The numbers

    steps against collection size
    space left per step
    time at one check per nanosecond

    How it works

    Every particle in the observable universe gets a number along a Hilbert curve, a line that folds back and forth to fill the whole sky without ever jumping. Because the numbers run in order through space, the first half of the numbers is one half of the sky, and so is every half of a half.

    So you only need one question at a time: is its number in the upper half of what is left? Each yes or no throws away half of everything. After about 266 answers only one particle is left, and the answers, written as bits, are its address.

    Shuffle the numbers and the trick dies: the lower half of the numbers is scattered everywhere, so a range of numbers says nothing about where to look. All that is left is checking particles one by one.

    Doubling the size of the universe costs one more question, not twice the work.

    steps = ⌈log₂ N⌉ = ⌈log₂ 10⁸⁰⌉ = 266N particles; each answer halves what is left, so after k answers N / 2ᵏ remain
    linear search ≈ N / 2 checkson average, with nothing to guide you: 5 × 10⁷⁹ checks for the universe
    2^(q − 1) − 1 < n ≤ 2^q − 1think of a number: q higher, lower or correct questions can single out at most 2^q − 1 numbers, so 1 to 1,000 needs 10 and 1 to 1,000,000 needs 20

    Think of a number is the same search on a line. The page always guesses the middle of what is left, so each higher or lower throws away half, and the ladder zooms in one row per question. Turn it round and the page hides a number: every guess is scored in bits, where a perfect halving earns 1 and a guess outside the range you already knew earns nothing.