#c #algorithm #sorting #search #binary-search
#c #алгоритм #сортировка #Поиск #двоичный поиск
Вопрос:
Если задан несортированный массив, который из следующих двух сценариев будет иметь меньшую временную сложность или будет работать лучше
- Двоичный поиск — сначала сортируя массив, а затем используя алгоритм двоичного поиска
- Последовательный поиск — по несортированному массиву
Итак, если для поиска элемента задан несортированный массив, следует ли нам отсортировать его, а затем применить двоичный поиск или напрямую применить алгоритм последовательного поиска к несортированному массиву.
Комментарии:
1. Это зависит от ситуации. Если запрос запрашивается только один, последовательный поиск должен быть лучше. Если для одного массива будет много запросов, сортировка требуется только один раз, и лучше использовать двоичный поиск.
2. Глядя на это с другой точки зрения: почему вы используете массив для поиска материала в первую очередь? Хранение ваших данных в хэш-таблице (
<unordered_set>) даст вам постоянное время доступа (за счет вставок).3. Для небольших наборов данных последовательный поиск превосходит двоичный поиск, особенно когда данные не отсортированы.
Ответ №1:
Оба существуют, потому что у обоих есть свои места, где они полезны.
Если вы будете выполнять поиск только один раз, последовательный поиск выполняется быстрее. Но если вы выполняете много запросов, то двоичный поиск выполняется быстрее. Учитывая, что сортировка есть O(n log(n)) , двоичный поиск становится таким же количеством операций, если вам нужно выполнять O(log(n)) поиск.
НО операции не создаются равными. В частности, для двоичного поиска требуются вопросы «да / нет», которые сложны для прогнозирования ветвлений. В результате, если вы ищете список из менее чем 100 целых чисел, двоичный поиск, вероятно, будет медленнее, чем последовательный поиск, потому что двоичный поиск имеет несколько остановок конвейера (каждый неверно предсказанный двоичный выбор), в то время как последовательный поиск имеет только один (когда вы находите искомый элемент).
Итак, если вы выполняете много поисковых запросов, и у вас либо много данных, либо сложные данные (например, строки), двоичный поиск лучше.