efficient search pseudocode to find maximum element satisfying equality

Question

I have as my range the closed set [0,100]. I have a function, f(), that can be evaluated on each element in the range. The function when evaluated on the range decreases monotonically. Task is to find the maximum element of the array whose functional value is equal to a given value, g. There are multiple elements who evaluate to g. Since we will have to discretize the range anyway, the maximum element in terms of that step size is what i am after. I want to do it in efficient way so linear search is bad.

xmax=-inf;
for x=0:h:100
    n=f(x)
    if n == g
        if x > xmax
            xmax = x;
        end
    end
end

So i assume binary search will get quicker results. But the ideal psuedocode doesn't exactly fit my exact requirement:-

      low = 0
      high = N - 1
      while (low <= high) {
          // invariants: value > A[i] for all i < low
                         value < A[i] for all i > high
          mid = (low + high) / 2
          if (A[mid] > value)
              high = mid - 1
          else if (A[mid] < value)
              low = mid + 1
          else
              return mid
      }
      return not_found // value would be inserted at index "low"

Can someone suggest an iterative search pseudocode or point to a source that solves my problem most efficiently? i am not interested in recursive solutions if an efficient iterative solution is available.

Answer 1

Using your pseudo-code as a starting point, I suggest the following modifications:

  low = 0
  high = 100
  result = NIL

  while (low <= high) {
      mid = ⌊(low + high) / 2⌋ // Round down after division.

      if (f(mid) < g) {        // Swapped > and < because f decreases.
          high = mid - 1
      } else if (f(mid) > g) { // Swapped > and < because f decreases.
          low = mid + 1
      } else {
          result = mid         // A possible result has been found, might 
          low = mid + 1        // not be maximal. Continue looking.
      }
  }

  return result                // This is the maximal result or NIL.

An implementation in e.g. JavaScript would look as follows:

// Find highest x with f(x) = g for monotonically decreasing f:
function find(f, g, low, high) {
  let result;

  while (low <= high) {
    let mid = low + high >> 1;
    let y = f(mid);
    
    if (y < g) {
      high = mid - 1;
    } else if (y > g) {
      low = mid + 1;
    } else {
      result = mid;
      low = mid + 1;
    }
  }
  return result;
}

// Example for range [0, 10]:
f = (x) => [10, 10, 9, 9, 9, 8, 6, 5, 5, 3, 1][x];
console.log(find(f, 9, 0, 9)); // 4