Поиск

Для эффективной работы с данными необходимо понимать как работают алгоритмы поиска, и какой из них лучше выбрать в определенной ситуации.

В данной статье я рассмотрю 3 вида поиска.

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

Он же известный как исчерпывающий, эффективен в небольших массивах, пример линейного поиска:

for i in range(array_len):

if target == array[i]:

return i

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

Бинарный поиск

Эффективен в больших отсортированных массивах, пример бинарного поиска:

Область поиска постоянно делится пополам, пока искомый элемент не будет найден.

Интерполяционный поиск

Эффективен в больших отсортированных массивах, в отличие от бинарного поиска нахождение элемента "угадывается" на основе диапазона значений в массиве и их распределения, что не всегда позволяет найти результат в один шаг, однако, тот оказывается достаточно близко. Предположим, в массиве содержится 1000 элементов со значениями от 1 до 100. Если наша цель — найти число 30, то его нужно искать в районе первой трети массива, где-то рядом с индексом 300.

Вывод

При работе с большим объемом данных стоит отдать предпочтение сложным алгоритмам поиска, и наоборот.

ссылка на git-репозиторий с алгоритмами поиска и тестами