ivan100sic's blog

Binary search on integers using C++20
By ivan100sic, 3 years ago, In English

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 - Guess the Permutation: 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.

  • Vote: I like it
  • +179
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Does this work for integers up to 1e18?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, this is a useful feature, but making mistakes while programming is part of the fun! So, if you don't mind, I will continue to write my own binary search :)

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +31 Vote: I do not like it

A cleaner way to do the same thing is to use std::ranges::partition_point, as mentioned here. The reason why it's called a partition point is that it gives the point $$$p$$$ for a range $$$[l, r)$$$ and predicate $$$f$$$ such that $$$f$$$ is true for everything in $$$[l, p)$$$ and false for everything in $$$[p, r)$$$. Again, this doesn't work for floats.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Very cool, and partition_point is more natural if the order is true..., false...

    → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Thanks for this interesting blog. The following is a slight update to your solution of the problem 1589D - Guess the Permutation using ranges::partition_point.

136152204

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it -10 Vote: I do not like it

    P.S. I have no personal problem at all with the downvotes. But it would be helpful if the downvoter is graceful enough to explain briefly what's disliked about the previous comment and the included submission.

    Thanks in advance.

    → Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Default is std::ranges::less and not std::less<bool>. It doesn't change anything tho

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You are right, I omitted this and assumed it was the same. Apparently std::ranges::less and std::less have very different semantics in the general case, but in case of boolean arguments, they are the same.

    → Reply