找到范围内符合条件的最大元素

Question

假设我有整数范围 [l, r) 和满足以下条件的函数 check(int idx)：有一个索引 t (l <= t < r) 使得对于每个 i (l <= i <= t) check(i) == true 和每个 j (t < j < r) check(j) == false。有没有找到索引 t 的标准方法？标准 binary_search() 需要带有两个参数的比较器，因此不能在此处应用（如果我错了请纠正我）。

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) 始终为假

下面是用于测试算法和输出行的源代码示例，以更好地理解其工作原理。您也可以 try it out here.

#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 at worst.

找到范围内符合条件的最大元素

Find the biggest element in range that matches condition

c++

binary-search