Loading...
Jovanna avatar 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;

    }

Тагове:
0
C++ Fundamentals
georgi.stef.georgiev avatar 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 е по-голямо от всички елементи във вектора.

Поздрави,

Жоро

1
Jovanna avatar Jovanna 186 Точки

Благодаря!!

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.