Помните, что binary search работает только с отсортированным списком. Он начинается с двух переменных l и r, которые представляют левую и правую границы, между которыми выполняется поиск name.
На каждом этапе создается переменная m = (l + r)/2 и сравнивает имя по этому индексу с искомым. Если имя то, что вы ищете, все готово. В противном случае, если имя больше , установите r на m и продолжайте; и установите l на m в случае, если он меньше.
Вот мой код:
int binarySearch(const vector <string> &names, string name){
int l = 0, r = names.size();
while(l != r){
int m = (l+r)/2;
if(names[m] == name){return m;}
else if(names[m] > name){r = m;}
else{
l = m;
}
}
return -1; // name does not exist in the list
}
Альтернативный способ реализовать двоичный поиск - реализовать его с помощью прыжки . Этот подход сохраняет одну переменную, curr, которая представляет индекс, сравниваемый в данный момент.
int curr = 0;
for(int i = names.size()/2; i >= 1; i /= 2){ // jump size
while(curr+i < names.size() && names[curr+i] <= name){
curr += i;
}
}
if(names[curr] == name){
// name was found at index curr
}
Оба этих подхода основаны на одной идее, и время их выполнения практически идентично. Использование любого из этих подходов должно работать для вашей программы.
В вашей программе также есть функция selectionSort(), которая, как я предполагаю, должна сортировать std::vector перед выполнением алгоритма двоичного поиска. Обратите внимание, что C ++ предоставляет функцию сортировки общего назначения, std::sort(), которая во многих случаях выполняется намного быстрее, чем сортировка по выбору. Чтобы использовать std::sort(), вы должны набрать #include <algorithm> где-нибудь в своей программе.