c++ - 未排序数组上 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(尽管这是对您的特定系统特定的未定义行为的利用，并且不能保证在其他系统上产生相同的结果)。