Xylenox's blog

1 line binary search in c++20
By Xylenox, history, 23 months ago, In English 
auto res = *ranges::partition_point(views::iota(lo, hi), check);

this returns the first $$$x$$$ in the range $$$[lo, hi)$$$ such that check(x) is not true, or $$$hi$$$ if it doesn't exist. Be careful to make sure the $$$lo$$$ and $$$hi$$$ are both integers of the same type, otherwise there is weird behavior.

example usage: 284450329

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

Comments Comments (4)
| Write comment?
»
23 months ago, hide # |
 
Vote: I like it -43 Vote: I do not like it

well known

→ Reply
»
23 months ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

It might be convenient for some of us,but not necessary.In fact,a simple binary search is easy to write.

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

You might wonder whether this dereferences end() when all values satisfy check. It does, but for views::iota(lo, hi), end() stores hi, and dereferencing that iterator returns the stored value.

libstdc++ does the same: end(), operator*.

→ Reply