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!
