Fastest Branchless Binary Search (mhdm.dev)
from tedu@azorius.net to programming@azorius.net on 11 Aug 2023 18: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