You can beat the binary search • Hacker News Board

Re: You can beat the binary search

#81

Post by hinkley » Thu, Apr 30, 2026, 6:44 PM UTC

ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

I swear I read an article about treaps but instead of being used to balance the tree, they used the weights to Huffman encode the search depth to reduce the average access time for heterogenous fetch frequencies.

I did not bookmark it and about twice a year I go searching for it again. Some say he’s still searching to this day.

Re: You can beat the binary search

#82

Post by darknoon » Thu, Apr 30, 2026, 6:45 PM UTC

locknitpicker wrote: post #78

ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

> If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. You don't even need priors. See interpolation search, where knowing the position and value of two elements in a sorted list already allows the search to make an educated guess about where the element it's searching for is by estimating the likely place it would be by inter…

This relies on knowledge of the distribution, just querying in the middle of A = [1, 2, 4, 8, 16, ..., 2^(n-1)] is slower than binary search

Re: You can beat the binary search

#83

Post by painted-now » Thu, Apr 30, 2026, 6:48 PM UTC

ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

> In mathematical language, searching a sorted list is basically inverting a monotonic function, by using a closed-loop control algorithm.

Never thought about it this way. Brilliant!

Re: You can beat the binary search

#84

Post by rixed » Thu, Apr 30, 2026, 7:00 PM UTC

ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

> it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic

Also if you do not learn anything about the data while performing the binary search, no? Like, if you are constantly below the estimate, you could gess that the distribution is biases toward large values and adjust your guess based on this prediction.

Re: You can beat the binary search

#85

Post by gobdovan » Thu, Apr 30, 2026, 7:06 PM UTC

thaumasiotes wrote: post #66

gobdovan wrote: post #30

I thought this would be about how you can beat binary search in the 'Guess Who?' game. There's a cool math paper about it [0] and an approachable video by the author. [1] [0] https://arxiv.org/abs/1509.03327 [1] https://www.youtube.com/watch?v=_3RNB8eOSx0

You can't beat binary search in Guess Who. From the abstract: >> Instead, the optimal strategy for the player who trails is to make certain bold plays in an attempt catch up. The reason that's optimal, if you're losing, is that you assume that your opponent, who isn't losing, is going to use binary search. They're going to use binary search because it's the optimal way to find the secret. Since you're behind, if you…

You're mixing two different objectives the paper presents. You can't beat binary search when the objective is to minimise the expected number of turns in a single player setting.

However, in a two player setting, using the strategies presented in the paper, you will beat an adversary that uses binary search in more than 50% of the games played.

Here's another visual demonstration: https://www.youtube.com/watch?v=zmvn4dnq82U

Re: You can beat the binary search

#86

Post by mvelbaum » Thu, Apr 30, 2026, 7:15 PM UTC

hinkley wrote: post #81

ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

I swear I read an article about treaps but instead of being used to balance the tree, they used the weights to Huffman encode the search depth to reduce the average access time for heterogenous fetch frequencies. I did not bookmark it and about twice a year I go searching for it again. Some say he’s still searching to this day.

https://arxiv.org/abs/2206.12110 ?

Re: You can beat the binary search

#87

Post by VorpalWay » Thu, Apr 30, 2026, 7:16 PM UTC

senfiaj wrote: post #63

cubefox wrote: post #16

Since binary search is already very fast with its O(log n) time complexity: are there any real world applications which could practically benefit from this improvement?

I guess it matters if you have to do lookup in a tight loop. If you do this occasionally, I think it's not worth it, especially for complex objects with custom comparators. The algorithm is still O(log(n)) just a more advanced "divide and conquer" with smaller constant.

I would expect the standard library of various languages to provide an optimised implementation such as this. Then everyone downstream benefits, and benefits from future improvements when compiled for a newer version of the language / executed under a newer version of the runtime.

You see this in rust, where they replaced the hash tables many years ago, the channel a couple of years ago, and most recently the sort implementations for both stable and unstable sort. I expect other languages / runtimes do similar things over time as well as CPUs change and new approaches are discovered.

Re: You can beat the binary search

#88

Post by molf » Thu, Apr 30, 2026, 7:27 PM UTC

rixed wrote: post #84

ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

> it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic Also if you do not learn anything about the data while performing the binary search, no? Like, if you are constantly below the estimate, you could gess that the distribution is biases toward large values and adjust your guess based on thi…

It's not possible to learn anything about other elements when performing binary search, _except_ the only thing there is to learn: if the target is before or after the recently compared element.

If we would guess that there is a bias in the distribution based on recently seen elements, the guess is at least as likely to be wrong as it is to be right. And if we guess incorrectly, in the worst case, the algorithm degrades to a linear scan.

Unless we have prior knowledge. For example: if there is a particular distribution, or if we know we're dealing with integers without any repetition (i.e. each element is strictly greater than the previous one), etc.

Re: You can beat the binary search

#89

Post by 10000truths » Thu, Apr 30, 2026, 7:33 PM UTC

lalitmaganti wrote: post #74

I also wrote recently [1] about Exponential Search [2] which is another algorithm if you need to repeatedly binary search in an array where the elements you're searching are themselves are sorted. It allowed for an 8x speedup in our workload! [1] https://lalitm.com/post/exponential-search/ [2] https://en.wikipedia.org/wiki/Exponential_search

Exponential search is useful when you're querying a REST API that addresses resources with sequential IDs, and need the last ID, but there's no dedicated endpoint for it:

  HEAD /users/1 -> 200 OK
  HEAD /users/2 -> 200 OK
  HEAD /users/4 -> 200 OK
  ...
  HEAD /users/2048 -> 200 OK
  HEAD /users/4096 -> 404 Not Found

And then a binary search between 2048 and 4096 to find the most recent user (and incidentally, the number of users). Great info to have if you're researching competing SaaS companies.

Re: You can beat the binary search

#90

Post by nullc » Thu, Apr 30, 2026, 7:45 PM UTC

You can improve interpolated search by monitoring progress and if it's not converging fast enough, alternate with bisection steps. (and, as clear from the article, switch to linear/vector scanning when the range is small emough).

Often when an interpolated search is wrong the interpolation will tend to nail you against one side or the other of the range-- so the worst case is linear. By allowing only a finite number of failed probes (meaning they only move the same boundary as last time, an optimally working search will on average alternate hi/lo) you can maintain the log guarantee of bisection.