beautiful binary search https://probablydance.com/2023/04/27/beautiful-branchless-binary-search/

bsearch.cc

#include <algorithm>
#include <cassert>
#include <random>
#include <vector>

constexpr unsigned int bit_floor(unsigned int num) {
  return num == 0 ? 0 : 1 << (31 - __builtin_clz(num));
}

template <typename It, typename T, typename Cmp>
It my_lower_bound(It begin, It end, const T &value, Cmp &&compare) {
  // returns the first element that compare(element, value) is false
  if (end <= begin)
    return end;
  size_t length = end - begin;
  size_t step = bit_floor(length);
  if (step != length && compare(begin[step], value)) {
    begin = end - step;
  }
  for (step /= 2; step; step /= 2) {
    if (compare(begin[step], value))
      begin += step;
  }
  if (compare(begin[0], value))
    begin += 1;
  return begin;
}

int main() {
  std::random_device rd;
  std::mt19937 gen(rd());
  std::uniform_int_distribution<int> length_dist(0, 10000);
  std::uniform_int_distribution<int> value_dist(0, 1000);

  std::vector<int> vec;
  for (int t = 0; t < 1000; ++t) {
    int n = length_dist(gen);
    vec.resize(n);
    for (auto &x : vec)
      x = value_dist(gen);
    std::sort(vec.begin(), vec.end());
    int value = value_dist(gen);

    auto it = std::lower_bound(vec.begin(), vec.end(), value);
    assert(it == vec.end() || *it >= value);
    assert(it == vec.begin() || *(it - 1) < value);
    auto my = my_lower_bound(vec.begin(), vec.end(), value,
                             [](int a, int b) { return a < b; });
    assert(it == my);
  }
}