Алгоритмы поиска

Алгоритмы поиска значения в массиве данных могут не иметь никаких особых требований к входным данным, и такие алгоритмы мы сравним между собой. Если же о входных данных заранее кое-что известно (например, что они упорядочены по алфавиту), то для таких данных могут быть применены другие, более быстродействующие алгоритмы.

Итак, по порядку от самого простого для понимания, с иллюстрацией кодом на  JavaScript. Для всех алгоритмов A — массив входных данных, n — его длина, x — значение, которое хотим найти. Нас будет интересовать индекс элемента массива, имеющего искомое значение. Если результат не найден, то возвращается специальное значение «NOT FOUND».

Линейный поиск

Самый простой метод. Перебираем последовательно все элементы массива и каждый сравниваем с искомым значением. Если они равны, то запоминаем индекс. Слабость алгоритма в том, что нам приходится перебирать все элементы, вне зависимости от того, где находится искомый элемент.

Реализация на JavaScript:

Так как алгоритм всегда проходит n итераций, соответственно, можно сказать, что его быстродействие θ(n). (смотри статью про асимптотические нотации).

Усовершенстованный линейный поиск

На самом деле первый алгоритм был несколько надуманным, потому что нет смысла перебирать все оставшиеся значения в массиве, если мы уже нашли искомое. Вот эта идея тут и реализуется.

Поскольку здесь мы не всегда пробегаем по всем значениям, то быстродействие алгоритма (по-научному -его асимптотическая сложность) очень разнится для самого плохого и самого хорошего случаев — от θ(1) до θ(n). Можно сказать, что алгоритм имеет O(n).

Линейный поиск со сторожем (sentinel)

Здесь идея в том, что мы сохраняем последний элемент массива во временной переменной, чтобы на его место записать искомое значение. Это нужно, чтобы вместо цикла for использовать while без риска получить зацикливание, если в массиве не окажется искомой величины. В целом, все эти пляски подразумевают сокращение сравнений в каждой итерации с двух до одного. В описанных выше алгоритмах нам нужно проверить i<n, а затем A[i]=x. В данном же алгоритме проверка одна. Дает ли это выигрыш — зависит от конкретного языка программирования и процессора.

Цена одной итерации здесь может быть ниже, чем у улучшенного линейного поиска, но в асимтотической нотации всё то же самое: от θ(1) до θ(n) и O(n).

Рекурсивный линейный поиск

Тут всё то же самое, только с использованием рекурсии. Просто для иллюстрации.

Двоичный поиск

Этот алгоритм подразумевает, что входной массив уже отсортирован (например, по алфавиту). Только в этом случае можно применять двоичный поиск. Здесь в каждой итерации массив делится на две части, и мы сравниваем срединное значение с искомым. Соответственно, принимаем решение, что может находиться только в левой или только в правой части массива (оказалось больше или меньше границы раздела). Отсекаем ту часть, в которой искомого значения быть не может, таким образом, сразу же уменьшая количество итераций в два раза. Так делаем на каждой следующей итерации, пока «граничное» значение не окажется тем, что мы ищем.

Реализация на JavaScript:

Быстродействие (асимптотическая сложность) этого алгоритма O(lb(n)). Здесь lb(n) — это логарифм по основанию 2 (двоичный логарифм).

Рекурсивный двоичный поиск

То же самое, но с применением рекурсии:

 

 

Поделиться: Share on LinkedIn
Linkedin
Share on VK
VK
Share on Facebook
Facebook
0Share on Google+
Google+
0Tweet about this on Twitter
Twitter

Оставить комментарий

Ваш e-mail не будет опубликован.

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.

Яндекс.Метрика