cpp 中未排序数组上的 lower_bound 的行为

Question

我想问 cpp ( C++ ) 中的 lower_bound 当应用于未排序的数组时表现如何。我的意思是当我运行以下程序时。

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int arr[]={8,9,10,1,2,3};
    auto itr= lower_bound(arr,arr+6,7);
    cout<<*itr<<endl;
}

它的输出为“2”。但根据 lower_bound 的定义，它将迭代器提供给第一个失败的 '<' 和 'val' 元素。那么根据这个定义，答案不应该是‘8’吗，因为“8不小于7”。我知道它适用于排序数组，但我想知道这个值背后是否有逻辑，或者它是一个垃圾。

谢谢。

Answer 1

由于违反了提供排序数组的前提条件，因此行为未定义。您的代码两次演示了未定义的行为：首先，当您将无序数组传递给 时lower_bound，第二次，当您取消引用iter而不将其与arr+6第一个进行比较时。

不过，很容易看出发生了什么：背后的算法lower_bound是基本的二分搜索。你给算法一个数组，它把它们分成两半，并检查中间的项目。您提供了偶数个项目，有两个数字可以被认为是“在中间” - 10 和 1。看起来算法选择了 ，将1其与您的搜索项目 7 进行比较，并在上半部分继续搜索数组，检查 2 和 3，最后返回指向数组末尾的指针。

当您取消引用该指针时，您会得到垃圾；不幸的是，它恰好与数组的元素之一匹配，即 2，导致您得出错误的结论。

按如下方式更改代码以查看实际返回的内容：

int arr[]={8,9,10,1,2,3, -1};

现在取消引用索引 6 处的元素是有效的；您的代码可能应该打印-1（尽管这是对特定于您的特定系统的未定义行为的利用，并且不能保证在其他系统上产生相同的结果）。