### nor's blog

By nor, 3 years ago,
• +246

| Write comment?
 » 3 years ago, # |   +20 Another great blog by nor sir!
 » 3 years ago, # |   +27 norz
 » 3 years ago, # |   +16 orz sir!!
 » 3 years ago, # | ← Rev. 2 →   0 Read the last line of this blog (thank me later)https://codeforces.com/blog/entry/92248
 » 3 years ago, # |   +25 You briefly mentioned this, but partition_point with iota_view is kind of nice to use now: template Integer find_first_false(Integer l, Integer r, F &&f) { return *ranges::partition_point(ranges::views::iota(l, r), f); } 
•  » » 3 years ago, # ^ |   +33 Yeah, that's correct. I have used it in a past submission once, and it was one of the reasons why I wanted to write this blog: https://codeforces.com/contest/1550/submission/132417058
 » 3 years ago, # |   +20 starred, will read it later , too lazy to read such long blog right now.Thanks for such helpful blog.
 » 3 years ago, # |   +16 Another top contributor in making. Orz.
 » 3 years ago, # |   0 Why not mid = (l + r) / 2? It is easier and faster to write in all [l, r) algorithms(segment tree, binary search).
•  » » 3 years ago, # ^ |   +10 may overflow ?
•  » » » 3 years ago, # ^ | ← 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 years ago, # ^ |   +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 years ago, # ^ | ← 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 years ago, # ^ | ← 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.
•  » » 14 months ago, # ^ |   -15 mid=l+r>>1 is faster because >>1 is much faster than /2, and it also saves a byte:)
 » 3 years ago, # |   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.
 » 14 months ago, # |   +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?
•  » » 14 months ago, # ^ |   +8 Thanks for pointing it out! Fixed.
 » 14 months ago, # | ← Rev. 6 →   -8 Nvm
•  » » 14 months ago, # ^ |   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").
•  » » » 14 months ago, # ^ |   -8 Yes, I missed that you have my implementation in the blog.
 » 12 months ago, # | ← Rev. 2 →   0 amazing. I was facing much trouble in implementing BS. But, sir you have explained clearly. Thanks a lot.
 » 11 months ago, # |   0 Hi nor. Thanks for this great blog! Can you/someone else explain this behaviour? Or is it passing due to weak test cases?
•  » » 11 months ago, # ^ |   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.
•  » » » 11 months ago, # ^ |   0 Thanks, got it!
 » 11 months ago, # |   0 Great blog "Binary searching on the answer" problems stucked me twice recently... T.T https://atcoder.jp/contests/abc155/tasks/abc155_d https://codeforces.com/problemset/problem/1852/A