无法正确实现 upper_bound()

Question

我在二分搜索实现上遇到了很多困难，尤其是

• 如何选择高和低（或r和l）
• while循环条件中是否添加等号
• 是否更新r=mid或r=mid-1

我试图实施upper_boundfrom STL，但无法得到正确的答案。这是我的代码。

#include<iostream>
#include<vector>
#include<climits>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n+2);
    // adding 0 in front to avoid out of bounds error 
    // when looking for a[m-1]
    a[0]=0;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    // adding a big element at the end to return that index
    // when required element is greater than all elements
    a[n]=INT_MAX;

    // q queries for testing purposes
    int q;
    cin >> q;
    while(q--){
        // we return m-1 at the end, so l and r capture 
        // all possible outputs, inclusive bounds
        int l=1, r=n+1, m;
        int val;
        cin >> val;

        // always confused whether to put in 
        // the equality sign or not
        while(l<=r){
            m=(l+r)/2;
            // break when the required element is found
            if(a[m]>val && val>=a[m-1])
                break;
            else if(val>a[m])
                l=m+1;
            else
                r=m-1;
        } 
        cout << m-1 << " ";
    }

    return 0;
}

用于测试的示例输入：

7
3 6 8 10 11 14 22
6
0 10 1 3 15 28

如果我使用 STL 中的 upper_bound，预期输出：

0 4 0 1 6 8

得到了我的实施的输出

0 2 0 1 6 6

我得到了错误的输出，但我不明白为什么。我可以记住任何简化以避免此类实现错误或简化我对如何编写二分搜索代码的理解吗？

Answer 1

要设计正确的二分查找函数，不要试图猜测解决方案，因为很难猜对。使用循环不变量的方法。upper_bound假设，我们想从标准库实现：

template<class It, typename T>
It upper_bound(It first, It last, const T& value);

根据规范，upper_bound我们正在寻找过渡点pt，使得范围内[first, pt)所有元素都有值<= value，并且范围内[pt, last)所有元素都有值> value。

让我们引入两个迭代器（指针）left和right循环不变量：

• 在范围内[first, left)所有元素都有值<= value，
• 范围内[right, last)所有元素都有值> value。

这些范围代表了迄今为止所研究的元素。最初，left = first、 和right = last，因此两个范围都是空的。在每次迭代中，其中一个都会被扩展。最后， ，所以现在检查left = right整个范围。[first, last)从上面的定义可以看出pt = right.

下面的算法实现了这个想法：

template<class It, class T>
It upper_bound(It first, It last, const T& value) {
    auto left  = first;
    auto right = last;

    while (left < right) {
        const auto mid = left + (right - left) / 2;
        if (*mid <= value)        // update left,  i.e. expand [first, left)
            left = mid + 1;
        else                      // update right, i.e. expand [right, last)
            right = mid;
    }

    return right;
}

请注意，我们正在处理半开范围。我们希望将mid其纳入扩展范围之一。这就是为什么我们将left右（排除）边界设置为，而将左（包含）边界mid + 1设置为。rightmid

所有这些都可以很容易地用索引重写，并作为简单的练习。