查找范围内与条件匹配的最大元素

Question

假设我有整数范围[l，r)和一个满足以下条件的函数check(int idx)： 有一个索引 T (L <= t <r)，使得对于每个><= i <= t)check(i) == true并且对于每个 j (t

Answer 1

假设您正在搜索连续的整数范围(而不是索引数组)，我建议您进行二分搜索：

int find_t(int l, int r) {
// Preconditions
assert(check(l) == true);
//assert(check(r) == false); // this precondition is not mandatory
int max_idx_true = l; // highest known integer which satisfies check(idx) == true
int min_idx_false = r; // lowest known integer which satisfies check(idx) == false
while (max_idx_true+1 < min_idx_false) {

int mid_idx = (max_idx_true+min_idx_false)/2;
if (check(mid_idx)) max_idx_true = mid_idx;
else min_idx_false = mid_idx;
}
int t = max_idx_true;
// Postconditions
assert(check(t) == true);
assert(t+1 == r || check(t+1) == false);
return t;
}

此算法缩小最接近的整数，其中 check(idx) 为真，下一个为假。在您的情况下，您正在寻找对应于max_idx_true的 t。

应该注意的是，必须满足以下先决条件才能正常工作：

• l<r>
• check(l)是真的
• 对于任何idx，如果check(idx)为真，则check(idx-1)总是为真
• 对于任何idx，如果check(idx)是假的，那么check(idx+1)总是假的

下面是一个源代码示例，用于测试算法和输出行，以更好地了解其工作原理。您也可以在这里尝试一下。

#include <iostream>
#include <cassert>
using namespace std;
// Replace this function by your own check
bool check(int idx) {
return idx <= 42;
}
int find_t(int l, int r) {
assert(check(l) == true);
//assert(check(r) == false); // this precondition is not mandatory
int max_idx_true = l; // highest known integer which satisfies check(idx) == true
int min_idx_false = r; // lowest known integer which satisfies check(idx) == false
int n = 0; // Number of iterations, not needed but helps analyzing the complexity
while (max_idx_true+1 < min_idx_false) {
++n;

int mid_idx = (max_idx_true+min_idx_false)/2;
// Analyze the algorithm in detail
cerr << "Iteration #" << n;
cerr << " in range [" << max_idx_true << ", " << min_idx_false << ")";
cerr << " the midpoint " << mid_idx << " is " << boolalpha << check(mid_idx) << noboolalpha;
cerr << endl;

if (check(mid_idx)) max_idx_true = mid_idx;
else min_idx_false = mid_idx;
}
int t = max_idx_true;
assert(check(t) == true);
assert(t+1 == r || check(t+1) == false);
return t;
}
int main() {
// Initial constants
int l = 0;
int r = 100;
int t = find_t(l, r);
cout << "The answer is " << t << endl;
return 0;
}

二分搜索的主要优点是它找到的候选者的复杂性仅为 O(log2(N))。

例如，如果您初始化int l = -2000000000并int r = 2000000000(+/- 20亿)，则需要知道大约 40 亿个数字的答案，但最坏的迭代次数将是 32

。