14. Алгоритмы поиска и выборки. Последовательный поиск, Двоичный поиск

Меню

Лекция 14. Алгоритмы поиска и выборки. Последовательный поиск, Двоичный поиск

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

Основные типы алгоритмов поиска:

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

Алгоритмы выборки:

Выборка с возвращением - каждый элемент из набора данных может быть выбран более одного раза.
Выборка без возвращения - каждый элемент выбирается только один раз.
Стратифицированная выборка - популяция делится на несколько страт, из которых делается выборка.
Кластерная выборка - популяция разделяется на кластеры, выборка производится из случайных кластеров.

Поисковые алгоритмы в структурах данных:

Поиск в деревьях (например, в бинарных деревьях поиска)
Поиск в графах (например, поиск в ширину и поиск в глубину)

Оптимизация алгоритмов поиска:

Индексация - создание индексов для ускорения поиска.
Кэширование - сохранение результатов поиска для быстрого повторного доступа.
Распределенный поиск - использование нескольких машин для обработки больших объемов данных.

Применение алгоритмов поиска и выборки:

Базы данных - поиск данных среди миллиардов записей.
Поисковые системы - алгоритмы ранжирования и индексации для обработки и поиска информации в интернете.
Рекомендательные системы - использование алгоритмов выборки для предложения продуктов или услуг.

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

14.2. Последовательный поиск
Когда элементы данных хранятся коллекцией в виде списка, мы говорим, что между ними линейные или последовательные отношения. Каждый элемент хранится на определённой позиции относительно прочих. В списках Python она задаётся индексом данного элемента. Поскольку значения индексов упорядочены, мы имеем возможность последовательно проходить по ним. Этот процесс приводит к нашей первой поисковой технике - последовательному поиску.

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

Рисунок 1: Последовательный поиск в списке целых чисел

Реализация этого алгоритма на Python показана в CodeLens 1. Функция требует список и элемент, который мы ищем, а возвращает логическое значение, говорящее о его присутствии. Булева переменная foundинициализируется значением False, и если элемент обнаруживаем в списке, то ей присваивается True.


def sequentialSearch(alist, item):
2	    pos = 0
3	    found = False
4	
5	    while pos < len(alist) and not found:
6	        if alist[pos] == item:
7	            found = True
8	        else:
9	            pos = pos+1
10	
11	    return found
12	
13	testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
14	print(sequentialSearch(testlist, 3))
15	print(sequentialSearch(testlist, 13))

Анализ последовательного поиска
Для анализа алгоритма поиска нам нужно определиться с базовым блоком вычислений. Напомним, что обычно им является распространённый шаг, который необходимо повторять, чтобы решить задачу. Для поиска имеет смысл подсчитывать количество производимых сравнений. Каждое сравнение может (или не может) обнаружить искомый элемент. В дополнение мы сделаем ещё одно предположение. Список будет неупорядочен, т.е. элементы размещаются в нём случайным образом. Другими словами, вероятность найти искомое на данной позиции одинакова для всех индексов.
Если элемент не в списке, то единственный способ узнать об этом - сравнить его со всеми имеющимися значениями. Если имеется n элементов, то последовательный поиск потребует n сравнений, чтобы открыть отсутствие элемента. Если же элемент в списке присутствует, то анализ уже не столь очевиден. Вообще, есть три различных сценария. В лучшем случае мы найдём элемент на первой же позиции, которую рассмотрим, - в самом начале списка. Нам потребуется всего одно сравнение. В худшем случае мы будем искать элемент, пока не дойдём до самого последнего - n-го - сравнения.
Что можно сказать о среднем случае? В нём мы найдём элемент примерно на середине списка. Т.е. нам надо будет сравнить n2 значения. Однако, напомним, что для больших n коэффициенты (вне зависимости от их величины) теряют значение при аппроксимации. Так что сложность последовательного поиска равна O(n). Таблица 1 суммирует результаты этих рассуждений:

Ранее мы предполагали, что элементы в нашей последовательности размещены произвольно, так что между ними нет относительного упорядочения. Что произойдёт с последовательным поиском, если элементы будут каким-либо образом упорядочены? Сможем ли мы получить возможность для более эффективной методики поиска?
Предположим, список значений был построен таким образом, что они расположены в нём по возрастанию, от наименьшего к наибольшему. Если искомый элемент есть в списке, то вероятность для него быть на любой из nпозиций такая же, как и раньше. Нам по-прежнему необходимо то же количество сравнений для поиска. Однако, для случая, когда элемент в списке отсутствует, у нас есть небольшое преимущество. Рисунок 2показывает процесс поиска алгоритмом числа 50. Заметьте, что элементы сравниваются последовательно вплоть до 54. В этот момент у нас имеется некая дополнительная информация. Не только то, что 54 - не тот элемент, который мы ищем, но и что элементы за 54-м однозначно не подойдут, поскольку список отсортирован. В этом случае алгоритму нет смысла идти дальше и просматривать всё до конца, чтобы сказать, что искомое не найдено. Он немедленно остановится. CodeLens 2 показывает этот вариант функции последовательного поиска.

Таблица 2 суммирует эти результаты. Заметьте, в лучшем случае мы обнаружим, что элемент не в списке, просмотрев всего одно значение. В среднем мы будем это знать, просмотрев n2 элементов. Однако, эта методика по-прежнему имеет O(n). Резюме: последовательный поиск улучшается при упорядочении списка только для случая, когда искомый элемент в нём отсутствует.

Реализация бинарного поиска
Существуют два способа реализации бинарного поиска:
1. Итерационный метод. При таком подходе используется цикл, тело которого повторяется, пока не найдется заданный элемент либо не будет установлено, что его нет в массиве. Например, в Python для этой цели удобно использовать цикл while.
2. Рекурсивный подход. В этом случае пишется функция, которая вызывает сама себя (рекурсивно), пока не будет найден искомый элемент в массиве.

Приведем примеры реализации этих методов на Python.
Пусть есть массив чисел [5, 8, 9, 1, 23, 7, 3, 0, 15], и необходимо найти позицию числа 5 в упорядоченном списке. На вход такой функции необходимо подать уже отсортированный массив, для этого воспользуемся встроенным методом sorted(), который упорядочивает массив данных по возрастанию.
Код, использующий итерационный подход, будет выглядеть так:

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

Принцип работы алгоритма бинарного поиска
Основная последовательность действий алгоритма выглядит так:

Сортируем массив данных.
Делим его пополам и находим середину.
Сравниваем срединный элемент с заданным искомым элементом.
Если искомое число больше среднего — продолжаем поиск в правой части массива (если он отсортирован по возрастанию): делим ее пополам, повторяя пункт 3. Если же заданное число меньше — алгоритм продолжит поиск в левой части массива, снова возвращаясь к пункту 3.

Блок-схема алгоритма двоичного поиска

Поиск позиции заданного элемента в списке


def findPosition(num_list, number):
first = 0
last = len(num_list) - 1
while first <= last:
middle = first + (last - first) // 2
if num_list[middle] == number:
return middle
elif num_list[middle] < number:
first = middle + 1
else:
last = middle - 1
return -1
num_list = sorted([5, 8, 9, 1, 23, 7, 3, 0, 15])
number = 5
print(findPosition(num_list, number))

При использовании рекурсивного поиска код на Python можно написать так:


def findPosition(num_list, number, first, last):
if last >= first:
middle = first + (last - first) // 2
if num_list[middle] == number:
return middle
elif num_list[middle] < number:
return findPosition(num_list, number, middle + 1, last)
else:
return findPosition(num_list, number, first, middle - 1)
else:
return -1
num_list = sorted([5, 8, 9, 1, 23, 7, 3, 0, 15])
number = 5
print(findPosition(num_list, number, 0, len(num_list) - 1))

В некоторых языках программирования, включая Python, есть готовые функции для выполнения бинарного поиска. Модуль бинарного поиска называется bisect. Проиллюстрируем его работу на примере:


from bisect import bisect_left
def findPosition(num_list, number):
pos = bisect_left(num_list, number)
if pos < len(num_list):
return pos
return False
num_list = sorted([5, 8, 9, 1, 23, 7, 3, 0, 15])
number = 5
print(findPosition(num_list, number))

В каких случаях используют бинарный поиск
Двоичный поиск подходит для нахождения позиций элемента в упорядоченном списке: в этом случае он эффективнее линейного, поскольку массив данных на каждом шаге разделяется надвое и одна половина сразу отбрасывается. Последовательная сложность двоичного метода в худшем и среднем случаях равна O(log n), в лучшем — O(1) (если обнаруживаем искомый элемент на первой итерации). Для сравнения: вычислительная сложность линейного поиска равна O(n) (обычный проход по всем элементам в поисках нужного).

У бинарного поиска есть недостаток — он требует упорядочивания данных по возрастанию. Сложность сортировки — не менее O(n log n). Поэтому, если список короткий, используется все-таки линейный поиск.

Разновидности алгоритма
На основе бинарного поиска разработано несколько дополнительных разновидностей поисковых алгоритмов:

однородный бинарный поиск, при котором аргумент поиска А сравнивается с ключом Ki, где i — золотое сечение интервала (оно выбирается так, чтобы отношение длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка);
троичный поиск, когда интервал делится на три части вместо двух. Обычно применяется для поиска положения экстремума функции;
интерполирующий поиск, который предсказывает позицию нужного элемента на основе разницы значений. Эффективен, если элементы распределены достаточно равномерно;
дробный спуск — применяется для ускорения двоичного поиска в многомерных массивах данных, и другие.

14.4. Тест