So I suck at binary search, and just mess around with +1s until it seems to work, get a WA or two, mess around with more +1s, and occasionally get it right by accident. But while talking to iframe_, I learned about a binary search implementation that is significantly more intuitive, cleaner, and shorter called Bitwise Binary Search. You can probably figure out how it works from just the name. Instead of storing a range with a left and right bound, you store it in a single int(or long). The current range of values in the nth iteration is the 1 through n-1th largest bits in the number to those bits followed by all 1s. This is fairly intuitive, as each binary search iteration will decrease the the search range by half. The first iteration will determine whether the largest bit of the integer is 1 or 0, and depending on which it is, this will limit the range to the bottom or top half. The rest of the bits work in a similar manner. You iteratively find the ith largest bit of the answer each time. There's a couple of really cool features that this has. First of all, it's easy to write:
int current = start;
for(int step = 1<<20; step > 0; step /= 2)
if(works(current+step)) current += step;
This is clearly a lot shorter than a normal binary search implementation, and the answer will be stored in current. But on top of that, this will, by default, work for both lowerbound and upperbound. It will find the most extreme value that works, whether works returns true for the bottom x values or top x. This is intuitive as well, so implementing it in contest will take minimal time. It can also be very easily adapted to floating point binary search on answers with similar syntax:
float current = start, maxstep = 1e6, minstep = 1e-6;
for(float step = maxstep; step >= minstep; step /= 2)
if(works(current+step)) current += step;
I finally learned binary search after reaching expert!
Fun fact: some LCA implementations use this binary search (called 'binary lifting')
https://cp-algorithms.com/graph/lca_binary_lifting.html
Everything that has "binary" in its name isn't automatically binary search. Binary lifting is completely separate technique from binary search.
actually, I would argue they are the same
I agree that LCA uses this binary search and also binary lifting, but they are still different things. This (binary search):
and this (binary lifting):
are completely different. But lca:
is a great example of this binary search
Yeah, I was talking about the second part...
The second part:
Doesn't use anything even remotely close to the binary search described in the blog.
Oops, my apologies, it seems like I made a typo. I meant the last part.
The works function in this case is
is_ancestor()and $$$i$$$ is $$$\log_2(\text{step})$$$.You can think of $$$\text{current}$$$ in the bitwise binary search as analogous to how far $$$u$$$ has been lifted up.
Binary lifting usually involves storing certain answers and then using them to answer queries in logN, usually for kth ancestor or something similar. Binary search doesn't involve any preprocessing, and it instead stores the range in each iteration of the query. While the logic of how this works is similar to the binary lifting approach of incremental jumping, I don't think that alone makes it binary lifting instead of search, especially when it functions as a search. I'd argue that the main difference between bin search and lifting is that lifting involves preprocessing so your binary search code can lookup in O(1).
At least someone here understands that binary search and binary lifting are two different things.
It's very useful, I think.
Anyway, I can use a algorithm better than $$$\Theta(\sqrt{n})$$$.
Feels like every month this gets reposted... good! I hope more learn about this technique.
It's technically $$$binary$$$ $$$lifting$$$. The idea in this implementation is not of $$$binary$$$ $$$search$$$, like you check the $$$mid$$$ $$$value$$$, but rather of $$$binary$$$ $$$ lifting$$$ and trying to see what is the $$$max$$$ $$$2^k$$$ I can add to my answer.
well it is exactly the same if you think about it. In the first iteration binary search checks if you can get L/2. If yes it checks 3L/4. So it tries adding L/4 to the answer just like lifting.
A simple example to describe the difference between binary search and binary lifting is LCA. In binary lifting the benefit we get is that our increase is always by some power of 2, that enables us to use spare table for LCA.
Another example, let's say if you want to binary search on a fenwick tree, now you will have $$$O(log^2$$$ $$$n)$$$ factor but if you use binary lifting, it will be $$$O(log $$$ $$$n)$$$.
For some simple problems, you can consider as them same, but if you go a little further, they are both different.
Binary lifting is just this part of lca:
It doesn't have to do anything with this blog
And this:
is NOT called binary lifting
Congrats on finding what works for you! For me normal binary search is more intuitive, I understand what invariants I need to mantain for left and for right and loop while (left + 1 < right), no ±1 anywhere else.
This can also be done if the range is not a power of two, just make sure to not to exceed the upper bound and potentially break it.
Also, you can make it a bit shorter:
This finds $$$t$$$ where $$$f(t) = 1$$$ and $$$f(t+1) = 0$$$, and (of course) $$$f$$$ is monotonic. The only real change from your code is removing that if condition.
This is fun, but if anyone still wants to learn about the classic binary search, you can just look up Errichto's blog. Never had any trouble with the implementation after this.