You can beat the binary search
lemire.me
You can beat the binary search
1–10 of 175 posts
Re: You can beat the binary search
#2The (AI generated?) image on this article is absolutely not helpful, and I think it's wrong based on how I read the article. Better not to have an image at all.
Re: You can beat the binary search
#3If you are storing 16-bit integers, wouldn't an 8kB bitmap be even faster?
Re: You can beat the binary search
#4The (AI generated?) image on this article is absolutely not helpful, and I think it's wrong based on how I read the article. Better not to have an image at all.
Agreed, it threw me off at first but the rest of the article was quite nice.
Re: You can beat the binary search
#5As a teenager I spent a weekend thinking that if binary search was good, because it cuts the search space in half at every step, then wouldn't a ternary search be better? Because we'd cut it into thirds at every step.
So instead of just comparing the middle value, we'd compare the one at the 1/3 point, and if that turns out to be too low then we compare the value at the 2/3 point.
Unfortunately although we cut the search space to 2/3 of what it was for binary search at each step (1/3 vs 1/2), we do 3/2 as many comparisons at each step (one comparison 50% of the time, two comparisons the other 50%), so it averages out to equivalence.
EDIT: See zamadatix reply, it's actually 5/3 as many comparisons because 2/3 of the time you have to do 2.
Re: You can beat the binary search
#6A beautiful algorithm.
Would there be any value in using simd to check the whole cache line that you fetch for exact matches on the narrowing phase for an early out?
Re: You can beat the binary search
#7As a teenager I spent a weekend thinking that if binary search was good, because it cuts the search space in half at every step, then wouldn't a ternary search be better? Because we'd cut it into thirds at every step. So instead of just comparing the middle value, we'd compare the one at the 1/3 point, and if that turns out to be too low then we compare the value at the 2/3 point. Unfortunately although we cut the se…
Did you continue by fantasizing about CPU's that contain ternary comparators?
Re: You can beat the binary search
#8[flagged]
Re: You can beat the binary search
#9As a teenager I spent a weekend thinking that if binary search was good, because it cuts the search space in half at every step, then wouldn't a ternary search be better? Because we'd cut it into thirds at every step. So instead of just comparing the middle value, we'd compare the one at the 1/3 point, and if that turns out to be too low then we compare the value at the 2/3 point. Unfortunately although we cut the se…
Isn't it a bit better on average, although not as much as you'd hoped? For example 19 steps of binary search get you down to 1/524288 of the original search space with 19 comparisons. 12 steps of ternary search get you down to 1/3^12 = 1/531441 of the original search space with, on average, 12 * 3/2 = 18 comparisons.
Re: You can beat the binary search
#10If you are talking smaller arrays, linear search with a sentinel value at the end is already tough to beat. The thing that sucks about that claim, is that "smaller" is such a nebulous qualifier that it is really hard to internalize.