5

我想问一下 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”。我知道它适用于排序数组，但我想知道这个值背后是否有逻辑或者它是垃圾。

谢谢。

4

1 回答 1

6

由于违反了提供排序数组的先决条件，因此行为未定义。您的代码两次演示了未定义的行为：首先，当您将无序数组传递给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（尽管这是针对您的特定系统的未定义行为的利用，并且不能保证在其他系统上产生相同的结果）。

于 2014-08-31T13:22:30.093 回答