Binary Search Algorithm to Find the Inverse of a Monotone Increasing Function

Given a Monotone Increasing Function f(x) and if y=f(x) is known, find the value of x.

Find the x by Binary Search Algorithm

Because function f(x) is monotone increasing meaning that for any x1<x2 we know f(x1) is smaller than f(x2). Thus in the domain of x, we can binary search to find the x in the given solution space.

int inverseFunction(function<int(int)> f, int y) {
   int left = -INT_MAX + 1;
   int right = INT_MAX;
   while (left <= right) {
      int mid = left + (right - left) / 2;
      int64_t midmid = f(midmid);
      if (midmid == y) return mid;
      if (midmid > y) {
         right = mid - 1;
      } else {
         left = mid + 1;
      }
   }
   // throw exception when can't find the solution f(x) = y
   throw new std::exception("no solution");
}

Here we have to be caution that the mid*mid may overflow the 32-bit integer thus we have to use a bigger type to accomodate the value. We also have to explicitly specify the starting lower/upper bounds.

However, we can use a starting value e.g. 1, and then determine the bounds more effectively.

int inverseFunction(function<int(int)>, int y) {
   int px = f(1);
   int left;
   int right;
   if (y > px) {
       left = 1;
       right = 1;
       while (f(right) < y) right <<= 1;
   } else {
       right = 1;
       if (f(0) < y) { 
          left = 0;  
       } else {
          left = -1;
          while ((f(left) > y) left = left * 2;
       }       
   }
   while (left <= right) {
      int mid = left + (right - left) / 2;
      int64_t midmid = mid * mid;
      if (midmid == y) return mid;
      if (midmid > y) {
         right = mid - 1;
      } else {
         left = mid + 1;
      }
   }
   // throw exception when can't find the solution f(x) = y
   throw new std::exception("no solution");
}

Here, we use O(log(y)) approach to determine the left and right boundaries.

–EOF (The Ultimate Computing & Technology Blog) —