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. There's a couple of really cool features this has. First of all, it's easy to write:

int v = start;

for(int step = 1<<20; step > 0; step /= 2)
  if(works(v+step)) v += step;

This is clearly a lot shorter than a normal binary search implementation, and the answer will be stored in v. 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!