алгоритм — бинарный поиск с векторами в переполнении стека

Question

алгоритм — бинарный поиск с векторами в переполнении стека

Я пишу метод бинарного поиска для университетского задания, и хотя я чувствую, что это правильный путь, я чувствую, что время выполнения больше, чем должно быть … Кто-нибудь видит какие-либо ошибки в этом? iterator это пользовательский класс, ничего особенного, делает то, что вы ожидаете. vec является вектором итераторов, которые указывают на больший связанный список того, что я «действительно» ищу

iterator searchVec(const I& item)
{
int left = 0;
int right = (int)vec.size()-1;
int mid = (right+left)/2;

while(*vec.at(left) != *vec.at(right)){
mid = (right+left)/2;
if (mid == 0 || mid == vec.size()-1){
//nothign else to search, we didnt find anything
return *vec.end();
}
if (*vec.at(mid) == item){
return vec.at(mid);
}
else if (item > *vec.at(mid)){
left = mid;
}
else if (item < *vec.at(mid)){
right = mid;
}
}
return vec.at(mid);
}

0

algorithm binary-search c++

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Некоторые мысли:

Ты используешь std::vector::at который медленный по сравнению с std::vector::operator[].
Вы не можете разыменовать vec.end(), Обычно он возвращается, если вы хотите сообщить вызывающей стороне, что элемент не найден. Но и здесь вы не возвращаете итератор vec, возможно, вам следует сообщить об этом с помощью логического параметра out или исключения.
Состояние цикла мне не подходит. Кажется должно быть left <= right вместо *vec[left] != *vec[right], Тогда цель цикла — выбрать элемент. Если мы вырвемся из цикла, то ничего не найдено.
Условие выхода бесполезно и не позволит найти первый и последний элемент, как указано в комментариях.
```
    if (mid == 0 || mid == vec.size()-1)
//nothign else to search, we didnt find anything
return *vec.end();
}
```

Вот слегка исправленный код:

iterator searchVec(const I& item)
{
int left = 0;
int right = (int)vec.size()-1;
int mid = (right+left)/2;

while(left <= right) // corrected condition
{
mid = (right+left)/2;
iterator it = vec[mid]; // avoid recomputing vec[mid]
if (*it == item) // this can be moved in a else {} statement,
return it;   // after the else if (no impact on performances I think)
else if (item > *it)
left = mid + 1; // you were not strictly decreasing the interval
else if (item < *it)
right = mid - 1; // same here
}
throw not_found();
}

0