Вопрос или проблема
Мне нужно использовать бинарный поиск, чтобы найти фильм, который вводит пользователь, однако, при поиске определенных фильмов или фильмов, которых нет в списке, поиск зацикливается. Мне сказали, что это связано с тем, что я не могу использовать “>” или “<” с строками, и мне нужно использовать функцию compare(), но у меня возникли трудности.
int main() { ...
pos = findMovieTitle(MovieArray, MOVIES_SIZE, Movies.title);
if(pos == -1) {
cout << Movies.title << " не найден" << endl << endl;
} else {
cout << "Название: " << MovieArray[pos].title << endl;
cout << "Год выпуска: " << MovieArray[pos].year << endl;
cout << "Выручка: " << MovieArray[pos].revenue << endl << endl;
}
...
}
int findMovieTitle(const Movies topMovies[], const int SIZE, string title) {
int first = 0;
int last = SIZE - 1;
int middle;
int pos = -1;
bool found = false;
while (!found && first <= last) {
middle = (first + last) / 2;
if(topMovies[middle].title == title) {
pos = middle;
found = true;
} else if (topMovies[middle].title.compare(title) > 0) {
last = middle - 1;
} else {
first = middle - 1;
}
}
return pos;
}
Я искал информацию и увидел, что если первая строка была больше, то возвращалось положительное целое число, так что я попробовал это, но это не решило проблему.
Эта строка:
first = middle - 1;
Должна быть:
first = middle + 1;
Это, вероятно, является основной причиной вашей ошибки и бесконечного цикла.
И если вам нужно использовать compare для вашего домашнего задания, вы можете оптимизировать, делая только одно сравнение вместо двух. Я подозреваю, что компиляторы все равно оптимизируют ваш код с включенными правильными флагами компиляции, но вот тонкая оптимизация.
int cmp = topMovies[middle].title.compare(title);
if(cmp == 0) {
pos = middle;
found = true;
} else if (cmp > 0) {
last = middle - 1;
} else {
first = middle - 1;
}
Ответ или решение
Применение функции compare() для строк в бинарном поиске
Бинарный поиск — это эффективный алгоритм поиска, который требует отсортированного массива для выполнения своих операций. Однако, при использовании строк в некоторых языках программирования, таких как C++, необходимо учитывать специфические нюансы сравнения строк. В вашем случае вы столкнулись с проблемой бесконечного цикла, что, вероятно, связано с неправильной логикой обновления индексов в алгоритме.
Проблема
Ваш код выполняет бинарный поиск названий фильмов, но застревает в бесконечном цикле при поиске некоторых названий. Как вы упомянули, вам указали на необходимость использования функции compare() вместо операторов > или < для сравнения строк. Причина заключается в том, что операции сравнения могут работать не так, как ожидается, из-за особенностей реализации строк в C++. Однако, главным источником проблемы в вашем коде является некорректное обновление значений индексов first и last.
Решение
Как упоминалось в ваших наблюдениях, необходимо изменить строку:
first = middle - 1;на
first = middle + 1;Таким образом, исправленный блок кода будет выглядеть следующим образом:
int findMovieTitle(const Movies topMovies[], const int SIZE, string title) {
int first = 0;
int last = SIZE - 1;
int middle;
int pos = -1;
bool found = false;
while (!found && first <= last) {
middle = (first + last) / 2;
int cmp = topMovies[middle].title.compare(title);
if(cmp == 0) {
pos = middle;
found = true;
} else if (cmp > 0) {
last = middle - 1;
} else {
first = middle + 1; // Исправлено здесь
}
}
return pos;
}Пояснение использования функции compare()
Функция compare() возвращает:
- 0, если строки равны;
- положительное значение (например, 1), если первая строка больше второй;
- отрицательное значение (например, -1), если первая строка меньше второй.
Это позволяет оптимизировать условные операторы, используя только одно сравнение для определения, находится ли искомый элемент перед, после или равен элементу в середине. Ваша оптимизированная версия кода значительно упрощает чтение и увеличивает производительность, поскольку выполняется всего одно сравнение вместо двух.
Заключение
В основном, ключ к успешной реализации бинарного поиска с использованием строк заключается в корректном обновлении индексов first и last и целесообразном применении метода compare(). Исправление логики поиска и использование функции compare() помогут вам избежать бесконечного цикла и обеспечат правильный результат поиска. Если потребуется дополнительная помощь с реализацией или уточнением дополнительных аспектов, не стесняйтесь задавать вопросы.