Блог пользователя Xylenox

1 line binary search in c++20
Автор Xylenox, история, 2 месяца назад, По-английски 
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

  • Проголосовать: нравится
  • +228
  • Проголосовать: не нравится

»
2 месяца назад, # |
  Проголосовать: нравится -43 Проголосовать: не нравится

well known

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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);
    → Ответить