Блог

Я хотел спросить, как ведет себя lower_bound в cpp (C ), когда он применяется к несортированному массиву. Я имею в виду, когда я запускал следующую программу.

 #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». Я знаю, что это работает с отсортированным массивом, но я хочу знать, есть ли логика за этим значением или это мусор.

Спасибо.

Поскольку предварительное условие предоставления отсортированного массива было нарушено, поведение не определено. Ваш код демонстрирует неопределенное поведение дважды: во-первых, когда вы передаете неупорядоченный массив в 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 (хотя это эксплойт неопределенного поведения, специфичного для вашей конкретной системы, и не гарантируется, что он даст те же результаты в других системах).