nor's blog

[Tutorial] Binary search and other "halving" methods
By nor, 3 years ago, In English

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

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

Comments Comments (27)
| Write comment?
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Another great blog by nor sir!
Sadge_pray

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

norz

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

orz sir!!

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Read the last line of this blog (thank me later)
→ Reply
»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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);
}
→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

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

Another top contributor in making. Orz.

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

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

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

    may overflow ?

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

      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

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

        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.

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

    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).

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

      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.

      → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

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

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

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.

→ Reply
»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks for pointing it out! Fixed.

    → Reply
»
12 months ago, # |
← Rev. 6   Vote: I like it -8 Vote: I do not like it

Nvm

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

    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").

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

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

      → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

"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?

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

    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.

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

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

→ Reply