Binary search and eps in comparisons

The usual wisdom about floating-point comparisons inside binary search is to make comparisons exact, to avoid losing precision (as opposed to comparison using some error tolerance denoted as eps). For example this:

for (int step = 0; step < 100; ++step) {
  double middle = (left + right) / 2;
  if (f(middle) > 0) right = middle; else left = middle;
}

is preferable to

for (int step = 0; step < 100; ++step) {
  double middle = (left + right) / 2;
  if (f(middle) > eps) right = middle; else left = middle;
}

when f is a monotonically increasing function, because even with small eps, there's a danger that the corresponding error in the binary search parameter will be much bigger. On the other hand, even if our comparison is incorrect for equal values due to rounding errors, the binary search will still converge correctly since equal values may only appear in one point and everything will be correct in points very close to it.

But all above is true only if f is monotonically increasing! If it is just non-decreasing, and has a plateau, going without eps gets you hugely incorrect results. This bit me today in the hard problem of SRM 508: my failed solution that passes after adding error tolerance to the last comparison in enough() (TopCoder login required).

I guess the lesson is that when trying to be too clever (instead if adding eps to all comparisons), one needs to be extra careful :-)