cpp 中lower_bound 在未排序数组上的行为 [英] Behavior of lower_bound in cpp on unsorted array

问题描述

我想问一下当 cpp ( C++ ) 中的 lower_bound 应用于未排序的数组时，它的行为如何.我的意思是当我运行以下程序时.

I wanted to ask how lower_bound in cpp ( C++ ) behaves when it is applied on unsorted array. I mean when I ran the following program.

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

it gave the output as '2'. But according to definition of lower_bound, it gives the iterator to first element which fails '<' with 'val'. So according to this definition, shouldn't the answer be '8', because "8 is not less than 7". I know it works on sorted array, but I want to know whether or not, there is a logic behind this value or is it a junk.

谢谢.

推荐答案

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

Since the precondition of supplying a sorted array has been violated, the behavior is undefined. Your code demonstrates undefined behavior twice: first, when you pass an unordered array to lower_bound, and second, when you dereference iter without comparing it to arr+6 first.

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

It is easy to see what is going on, though: the algorithm behind lower_bound is a basic binary search. You give the algorithm an array, it divides them in two halves, and checks the item in the middle. You supplied an even number of items, there are two numbers that can be considered "being in the middle" - 10 and 1. It looks like the algorithm picked 1, compared it to your search item 7, and continued search in the upper half of the array, checks 2 and 3, and finally returns the pointer pointing past the end of the array.

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

When you dereference that pointer, you get junk; unfortunately, it happens to match one of the elements of your array, i.e. 2, leading you to a wrong conclusion.

如下更改您的代码以查看实际返回的内容:

Change your code as follows to see what is actually returned:

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

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

Now dereferencing the element at index 6 is valid; your code should probably print -1 (although this is an exploit of undefined behavior specific to your particular system, and it is not guaranteed to produce the same results on other systems).

这篇关于cpp 中lower_bound 在未排序数组上的行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！