无法正确实现upper_bound（）

Question

我在二进制搜索实现方面特别费劲，

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

我正在尝试从upper_bound实现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);

根据specification的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，但是却将right（左（包括）边界）设置为mid。

所有这些都可以很容易地根据索引进行重写，而只是简单的练习。