Never write binary search again*!

Often, solving a problem involves finding the smallest integer satisfying some predicate. The C++20 Ranges library allows us to run generic algorithms on ranges. Ranges can be backed by real data, such as ranges constructed from std::vectors, or they could be purely logical, such as std::ranges::iota_view.

This class can construct views given two values. In case those values are integers, the constructed range supports random-access, meaning that random-access algorithms such as std::ranges::lower_bound can run efficiently i.e. in $$$O(\log n)$$$. For example, std::ranges::iota_view(0, 5) returns a view representing integers $$$[0, 1, 2, 3, 4]$$$.

If you need to find the smallest integer value $$$v$$$ between $$$l$$$ and $$$r-1$$$ inclusive satisfying a predicate $$$p$$$ with the binary search property, or $$$r$$$ if it doesn't exist, you can do this in one line of C++ code:

auto v = *std::ranges::lower_bound(std::ranges::iota_view(l, r), true, {}, p);

The first argument of lower_bound is the range. We'll run our search on integers in $$$[l, r)$$$. The second argument is the projected value we'll be looking for — true, since we want the predicate to be true. The third value is the comparison we'll run on projected values. By default it is std::less<boolean>, it can be used in binary search since false < true is true in C++. It is important to note that your predicate $$$p$$$ must satisfy the binary search property: $$$p(x)$$$ implies $$$p(x+1)$$$ on the searched range. In other words, $$$p$$$ returns false for the first few (possibly zero) values, then it returns true and keeps returning true as you increase the argument. The last argument is the projection. This can be a function that accepts an integer as an argument, and returns a boolean. Often this will be a lambda expression.

The best part is that everything is inlined by the C++ compiler, making it as efficient, or even better than writing binary search manually.

For an example, check out my solution for 1589D - Угадай перестановку: 136076858

I'd also mention that std::ranges::iota_view can also be used in a range for-loop, making the code very easy to write if you give it a shorter name like I did in my submission.

*Mind you, this doesn't work on floats.