←back to thread

Beautiful branchless binary search

(probablydance.com)
386 points ingve | 2 comments | 28 Apr 23 05:46 UTC | HN request time: 1.11s | source
Show context
tromp ◴[28 Apr 23 08:06 UTC] No.35738737[source]▶
The setup code to reduce the length to a 2-power can be avoided. I'm curious how well the following code performs in comparison:

    for (size_t length = end - begin; length != 0; length = (length + 1) / 2)
    {
        size_t step = length / 2;
        if (compare(begin[step], value))
            begin += step;
    }   
    return begin;
For odd lengths like 5, this splits the array in an even part of length 2, and an odd part of length 3, and then searches either part with length 3. So again there is some redundancy for non-2-powers.

While this code is simpler, it does require an extra division and increment in each loop iteration, so presumably it performs a little worse.

replies(1): >>35750752 #
1. teo_zero ◴[29 Apr 23 07:10 UTC] No.35750752[source]▶
Doesn't this run forever? Once length reaches 1 it will never go to 0.
replies(1): >>35750942 #
2. tromp ◴[29 Apr 23 07:46 UTC] No.35750942[source]▶
Oops; you're right. One possible fix is

    for (size_t length = end - begin; length != 1; length = (length + 1) / 2)
    {
        size_t step = length / 2;
        if (compare(begin[step], value))
            begin += step;
    }   
    return begin + compare(*begin, value);
but it admittedly detracts from the simplicity of the former...