即使在数组上做了一个上界，也超过了时间限制。

Question

使用的语言：C++14.我给了两个排序的数组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

导致大数组的时间限制。