Бинарный поиск, отсортированный массив
Я изучаю бинарный поиск, и базовое определение начинается с итератора первого элемента, а другого — до последнего. У вас также есть ключ, который является элементом, который вы ищете. Ключ сначала сравнивается со значением средней точки, а затем верхняя половина или нижняя половина удаляется в зависимости от того, больше или меньше ключ значения средней точки. И процесс продолжается до совпадения.
Разве этот метод не требует сортировки контейнера, который вы просматриваете? В противном случае я не вижу, каким образом сравнение между ключом и значениями в контейнере для исключения частей контейнера для просмотра является каким-либо конкретным использованием.
Решение
Да, это так.
В компьютерных науках алгоритм двоичного поиска или полуинтервального поиска находит положение указанного входного значения (поисковый «ключ») в массиве отсортировано по значению ключа.
Источник: Википедия: Алгоритм двоичного поиска, хотя любой другой достойный текст в алгоритме должен упомянуть, что массив должен быть отсортирован.
Другие решения
Ответ — да. Бинарный поиск предполагает, что вы сначала сортируете свой набор. Если я не ошибаюсь, любой алгоритм поиска с производительностью лучше, чем O (N), требует, чтобы ваш набор хранился в какой-то специальной структуре данных (отсортированный список, двоичное дерево, красно-черное дерево …).
Когда вы реализуете двоичный поиск набора, вы должны убедиться, что набор отсортирован первым. Обычно вы сначала сортируете список, а затем всегда добавляете элементы в нужном месте (чтобы убедиться, что новый набор все еще отсортирован). Предполагая, что вы также используете бинарный поиск, чтобы найти правильное место для добавления, добавление и поиск — это O (log2 (N)) в худшем случае.
Когда вы рассматриваете различные алгоритмы поиска, вы также должны учитывать основную структуру данных и стоимость добавления элемента в нее.
detector