Branchless binary search

gistfile1.cpp

// based on:
//   blog.demofox.org/2017/06/20/simd-gpu-friendly-branchless-binary-search

#include <cstdint>
#include <cstddef>

template <typename type_t, size_t size>
size_t binary_search(type_t val, const type_t (& data)[size]) {
    size_t pos = 0;
    size_t i = size >> 1;
    /* check that loop gets unrolled */
    for (;i;i>>=1) {
        pos += (data[pos + i] <= val) ? i : 0;
    }
    return pos;
}

int main() {
    int test[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
    return binary_search(3, test);
}