寻找满足等式的最大元素的高效搜索伪代码

Question

我的范围是闭集 [0,100]。我有一个函数 f()，可以对范围内的每个元素进行计算。在范围上评估的函数单调递减。任务是找到函数值等于给定值 g 的数组的最大元素。有多个元素的计算结果为 g。由于无论如何我们都必须对范围进行离散化，因此就步长而言，最大元素就是我所追求的。我想以有效的方式进行，所以线性搜索不好。

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

所以我认为二分查找会更快得到结果。但是理想的伪代码并不完全符合我的确切要求：-

      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"

有人可以建议一个迭代搜索伪代码或指向一个最有效地解决我的问题的来源吗？如果有有效的迭代解决方案，我对递归解决方案不感兴趣。

Answer 1

以您的伪代码为起点，我建议进行以下修改：

  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.

一个实现，例如JavaScript 将如下所示：

// 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

寻找满足等式的最大元素的高效搜索伪代码

efficient search pseudocode to find maximum element satisfying equality

arrays

search

pseudocode

binary-search

linear-search