Fastest Branchless Binary Search
(mhdm.dev)
from tedu@azorius.net to programming@azorius.net on 11 Aug 2023 20:09
https://azorius.net/g/programming/p/P9VrKNW322Pshj3YX2-Fastest-Branchless-Binary-Search
from tedu@azorius.net to programming@azorius.net on 11 Aug 2023 20:09
https://azorius.net/g/programming/p/P9VrKNW322Pshj3YX2-Fastest-Branchless-Binary-Search
template <class ForwardIt, class T, class Compare>
constexpr ForwardIt sb_lower_bound(
ForwardIt first, ForwardIt last, const T& value, Compare comp) {
auto length = last - first;
while (length > 0) {
auto rem = length % 2;
length /= 2;
if (comp(first[length], value)) {
first += length + rem;
}
}
return first;
}
Oh and I’m sorry about just thrusting C++ code on you. Rude, I know. You don’t really need to know C++ to understand this article, just iterators (first and last), basically pointers to elements in an array, though note they can point one past the last array entry.
#cxx #programming
threaded - newest