c++ - 即使在数组上执行了上限，也超过了时间限制

Question

使用的语言:C++ 14。

我得到2个排序数组A和B。现在，对于A中的每个元素，如果可能的话，我必须在B中找到一个更大的元素，并请注意，一旦我在B中为A中的特定元素找到了元素，我就可以仅在B中的索引之前搜索。
我正在做这样的事情:

int j=0;
for(i=0;i < A.size();i++)
{
    int index = upper_bound(B.begin()+j,B.end(),A[i]) - B.begin();
    if(index>=B.size()){
        break;
    }
    else{
        cout<<"For A[]"<<A[i]<<" element "<<B[index]<<" is greater "<<"\n";
        j = index + 1;
    }
}

即使我正在使用upper_bound 进行 二进制搜索时，程序仍会给出大型数组(例如大小为1000000)的时间限制超过。

我不知道为什么？

P.S:我知道可以在线性时间内使用2个指针来完成此操作，但是我想知道为什么我的解决方案失败。我是新来者，请帮帮我。

Answer 1

首先，请确保upper_bound中的第一个迭代器<=第二个迭代器，因为可能发生某个数目的情况，数组B中的最后一个元素大于它，所以现在，如果执行j = index + 1，它将是等于B.end()，现在搜索更大的元素将总是返回大于B长度的整数，这是不可能的。

其次，您的问题是:

int index = upper_bound(B.begin()+j,B.end(),A[i]) - B.begin();

这条线首先将第一个迭代器移动“j”，而不是在恒定时间内移动，然后应用upper_bound将导致时间复杂度为 o(n*n*log(n))
n:用于遍历A

n:以“j”步移动，在最坏的情况下可以为n

log(n):对于upper_bound

这导致较大阵列的时间限制。