Xylenox's blog

1 line binary search in c++20
By Xylenox, history, 7 weeks 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

»
7 weeks ago, # |
  Vote: I like it -43 Vote: I do not like it

well known

→ Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +70 Vote: I do not like it

    I didn't know it and am thankful for the blog poster sharing it :O

    → Reply
»
7 weeks ago, # |
  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
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this also applicable when $$$hi$$$ is 1e18 ?

→ Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use 1e18, too, when both lo and hi are of the same type.

    auto res = *ranges::partition_point(views::iota(0ll, (long long)1e18), check);
    → Reply