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