Skip to content

Instantly share code, notes, and snippets.

@scturtle
Created April 29, 2023 04:00
Show Gist options
  • Save scturtle/ac568be5a5259115c7c78c43041f40c5 to your computer and use it in GitHub Desktop.
Save scturtle/ac568be5a5259115c7c78c43041f40c5 to your computer and use it in GitHub Desktop.
#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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment