Разница между бинарным и линейным поиском

Бинарный поиск против линейного поиска

Линейный поиск, также известный как последовательный поиск, является самым простым алгоритмом поиска. Он ищет указанное значение в списке, проверяя каждый элемент в списке. Бинарный поиск - это также метод, используемый для поиска указанного значения в отсортированном списке. Метод двоичного поиска делит пополам количество проверенных элементов (в каждой итерации), сокращая время, необходимое для поиска данного элемента в списке.

Что такое линейный поиск?

Линейный поиск - это самый простой метод поиска, который последовательно проверяет каждый элемент в списке, пока не найдет указанный элемент. Входными данными для метода линейного поиска является последовательность (например, массив, коллекция или строка) и элемент, который необходимо найти. Вывод имеет значение true, если указанный элемент находится в предоставленной последовательности, или значение false, если его нет в последовательности. Поскольку этот метод проверяет каждый элемент в списке до тех пор, пока указанный элемент не будет найден, в худшем случае он будет проходить через все элементы в списке, прежде чем найдет требуемый элемент. Сложность линейного поиска составляет o (n). Поэтому он считается слишком медленным для поиска элементов в больших списках. Но это очень просто и легче реализовать.

Что такое бинарный поиск?

Бинарный поиск - это также метод, используемый для поиска указанного элемента в отсортированном списке. Этот метод начинается со сравнения искомого элемента с элементами в середине списка. Если сравнение определяет, что два элемента равны, метод останавливается и возвращает позицию элемента. Если искомый элемент больше среднего, он снова запускает метод, используя только нижнюю половину отсортированного списка. Если искомый элемент меньше среднего, он снова запускает метод, используя только верхнюю половину отсортированного списка. Если искомого элемента нет в списке, метод вернет уникальное значение, указывающее на это. Поэтому метод бинарного поиска делит пополам количество сравниваемых элементов (в каждой итерации) в зависимости от результата сравнения. Следовательно, бинарный поиск выполняется в логарифмическом времени, что приводит к средней (o n) средней производительности случая.

В чем разница между бинарным и линейным поиском?

Хотя и линейный поиск, и бинарный поиск являются методами поиска, они имеют несколько отличий. В то время как бинарный поиск работает в отсортированных списках, линейный поиск может работать и в несортированных списках. Сортировка списка обычно имеет в среднем сложность n log n. Линейный поиск проще и проще в реализации, чем бинарный поиск. Но линейный поиск слишком медленный, чтобы его можно было использовать с большими списками из-за его o (n) средней производительности регистра. С другой стороны, бинарный поиск считается более эффективным методом, который можно использовать с большими списками. Но реализация бинарного поиска может быть довольно сложной, и исследование показало, что точный код для бинарного поиска можно найти только в пяти из двадцати книг.