Discrete binary search

Question

Can someone please explain discrete binary search with an example?

I read about it on the above link, and got a basic idea about what it is, but I still don't understand the code part and how it is practically implemented.

Answer 1

Basically, assume that

• You have a function f(x) which is monotonically increasing (decreasing) on the interval [a, b].
• f(a) < C < f(b)
• You want to find x such that f(x) = C.

Then you can use binary search to find x. Essentially, you half the possible interval for the variable x each time.

To implement it, do something along the lines of:

#define EPS 1E-9

double f(double x)
{
   ///some monotonically increasing function on [a, b], for example f(x) = x^3:
   return x*x*x;
}

double binarySearch(double C, double a, double b)
{
   double low = a, high = b;
   double mid;
   while(abs(low-high) > EPS)
   {
      mid = low + (high - low) / 2;
      if f(mid) < C
          low = mid;
      else
          high = mid;
   }
   return mid;
}