lower_bound - бинарно търсене - Софтуерен университет

Jovanna 186 Точки

lower_bound - бинарно търсене

Моля за малко разяснение (код от лекцията за STL Algorithms ). Koга се влиза в първия else, нали когато it != nums.end() означава, че searchNum е намерен; и searchNum е == *it . Какво изключение хваща първия else?

vector<int> nums { 41, 45, 61, 231, 764 };

int searchNum = 62;

auto it = lower_bound(nums.begin(), nums.end(), searchNum);

if (it != nums.end()) {

if (searchNum == *it) {

cout << "found " << *it << " at " << it - nums.begin() << endl;

} else {

cout << searchNum << " can be inserted at " << it - nums.begin()

<< " and the numbers will remain sorted"<< endl;

}

} else {

cout << "not in range" << endl;

}

Тагове:

19/12/2017 01:12:46 C++ Fundamentals

Виж всички отговори

georgi.stef.georgiev 921 Точки

Best Answer

Здравей,

Последния else хваща ситуацията, в която търсеното число е по-голямо от всички числа в рамките на търсенето. Това е споменато и в документацията: http://en.cppreference.com/w/cpp/algorithm/lower_bound, макар и индиректно.

lower_bound говорихме, че връща позицията, на която е числото (ако го има,), или на която би стояло (ако го няма) в сортировката (затова има if-else в първия if).

По-стриктно казано, ако търсим X в range-а [begin, end) връща позицията на първия елемент E, за който (E < X) == false, тоест намира позицията първия елемент E, за който (E >= X) == true. Това означава, че ако всички елементи в range-а са по-малки от X, няма елемент, който да отговаря на условието, и тогава получаваме end, както получаваме и при find когато няма елемент, отговарящ на търсенето.

За примера - ако търсиш 765 в nums, търсенето ще върне nums.end(), защото 765 е по-голямо от всички елементи във вектора.

Поздрави,

Жоро

19/12/2017 14:18:44

Jovanna 186 Точки

Благодаря!!

19/12/2017 21:46:42

Виж всички отговори