# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
Another great blog by nor sir!
norz
orz sir!!
https://codeforces.net/blog/entry/92248
You briefly mentioned this, but partition_point with iota_view is kind of nice to use now:
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.net/contest/1550/submission/132417058
starred, will read it later , too lazy to read such long blog right now.Thanks for such helpful blog.
Another top contributor in making. Orz.
Why not mid = (l + r) / 2? It is easier and faster to write in all [l, r) algorithms(segment tree, binary search).
may overflow ?
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
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 likestd::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 useauto
rather than a template, then if you accidentally have the endpoints of the range of different types, then the call tostd::midpoint
fails to compile, which is also nice imo.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).
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. Usingl + 1 < r
should be fine, if we also check for certain bounds on the inputs of the function call.mid=l+r>>1
is faster because>>1
is much faster than/2
, and it also saves a byte:)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.
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?
Thanks for pointing it out! Fixed.
Nvm
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").
Yes, I missed that you have my implementation in the blog.
Hi nor. Thanks for this great blog! Can you/someone else explain this behaviour? Or is it passing due to weak test cases?
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.
Thanks, got it!