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

[Tutorial] Binary search and other "halving" methods
Автор nor, 3 года назад, По-английски

https://nor-blog.surge.sh/posts/2021-11-07-binary-search/

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

»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Another great blog by nor sir!
Sadge_pray

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

norz

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

orz sir!!

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Read the last line of this blog (thank me later)
→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

You briefly mentioned this, but partition_point with iota_view is kind of nice to use now:

template <class Integer, class F>
Integer find_first_false(Integer l, Integer r, F &&f) {
  return *ranges::partition_point(ranges::views::iota(l, r), f);
}
→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

starred, will read it later , too lazy to read such long blog right now.Thanks for such helpful blog.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Another top contributor in making. Orz.

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

Why not mid = (l + r) / 2? It is easier and faster to write in all [l, r) algorithms(segment tree, binary search).

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    may overflow ?

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

      I have never seen a task, where (l+r)/2 is a problem. But when I need to operate with numbers > 4*10^18, I use __int128

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +20 Проголосовать: не нравится

        That's correct. I use (l + r) / 2 in algorithms where these are just indices. However, while templating code (for instance in dynamic segtree), I prefer using stuff like std::midpoint and so on, since it makes it less error-prone. Just a matter of personal preference I guess.

        Another usecase of std::midpoint is that if you're templating some code and use auto rather than a template, then if you accidentally have the endpoints of the range of different types, then the call to std::midpoint fails to compile, which is also nice imo.

        → Ответить
  • »
    »
    3 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    main reason we that because that is buggy for negative integers due to rounding off error, hence you use that see the topcoder article on binary search.
    also for another version we have to use mid = l + (r — l + 1) / 2.
    but it will work for while(l <= r) version.
    i guess best version is while(l + 1 < r).

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      True. The corresponding bug can be seen in the case where $$$[l, r) = [-1, 0)$$$, and doing m = (l + r) / 2 gives you $$$m = 0$$$, and this can lead to an infinite loop.

      As I mentioned in the blog, using the floor version rather than the ceil version (while thinking in terms of $$$[l, r - 1]$$$ rather than $$$[l, r)$$$), i.e., m = (l + r - 1) / 2, will also work correctly for integer division, since it mimics the other ways (though the semantics of the choice of midpoint generally depend on the sign of the sum of $$$l, r$$$, and this just coincidentally works).

      Another point regarding overflow: r - l > 1 as mentioned in the blog can be buggy at times if the distance between $$$r, l$$$ doesn't fit in that integer type. Using l + 1 < r should be fine, if we also check for certain bounds on the inputs of the function call.

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

    mid=l+r>>1 is faster because >>1 is much faster than /2, and it also saves a byte:)

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

The way you explained inclusive and exclusive search is just one of its kind. I had my worst time understanding which implementation should be used for a particular problem. Even though, I am still biased towards one of them, this blog actually gives you good insights on when to prefer some implementation over the other.

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

Another way of looking at it is: everything in the range [l,ans) corresponds to true, and everything in the range [ans,r) corresponds to true.

nor is this a typo?

→ Ответить
»
12 месяцев назад, # |
← Rev. 6   Проголосовать: нравится -8 Проголосовать: не нравится

Nvm

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

    That's the implementation I use in this blog as well (you have a bug though, $$$R$$$ should be $$$n$$$ instead if your search space is $$$[0, n - 1]$$$). I think of it as bringing two borders together (the "already known values").

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

      Yes, I missed that you have my implementation in the blog.

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

"Initially, we have zero information about any element of b, so it is better to force these ranges to be empty ranges" i did not get this line. Can you explain? why do we force it to be empty and how by l0-1 and r0+1 it becomes empty?

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

amazing. I was facing much trouble in implementing BS. But, sir you have explained clearly. Thanks a lot.

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

Hi nor. Thanks for this great blog! Can you/someone else explain this behaviour? Or is it passing due to weak test cases?

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

    Probably because of weak tests. You should try to understand what invariant the binary search keeps at each iteration, because in any binary search problem, you exploit the invariant at the end to claim that the found index is the answer. Thinking about the invariant will also fix your indices.

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

Great blog "Binary searching on the answer" problems stucked me twice recently... T.T https://atcoder.jp/contests/abc155/tasks/abc155_d https://mirror.codeforces.com/problemset/problem/1852/A

→ Ответить