Алгоритмы поиска, сравнение алгоритмов. Лекция 6

1.

Методы программирования
Лекция 6. Вводная лекция.
Лектор: Крючков Алексей Вячеславович

2.

Изучаемые вопросы
6.1. Описание методов поиска
6.2. Оценка методов поиска
Крючков А.В.
2

3.

Вопрос 1. Описание методов поиска.
1.1. Бинарный (двоичный) поиск
В информатике бинарный или двоичный поиск
(полуинтервальный поиск, или двоичная
выборка) – это такой процесс, при котором
целевое значение ищут ТОЛЬКО В
ОТСОРТИРОВАННОМ МАССИВЕ.
В отличие от рассмотренных в предыдущей
лекции методов поиска данный метод выполняет
первое сравнение, начиная не с первого и не с
последнего элемента. В числовом массиве на
первом шаге он находит элемент с индексом,
равным половине его длины.
Крючков А.В.
3

4.

Вопрос 1. Описание методов поиска.
1.1. Бинарный (двоичный) поиск
Если элемент с данным индексом не соответствует критерию поиска, то метод
выбирает половину массива, в которой может находится значение критерия.
Вторая половина массива отбрасывается.
Если значение критерия больше значения элемента с индексом, равным
половине длины массива, то отбрасывается условно левая половина массива.
Если наоборот, то правая. В оставшейся половине массива действие повторяется:
- находится условно средний элемент сначала оставшейся половины массива, со
значением которого сравнивается значение критерия поиска;
- если значение критерия больше значения выбранного элемента, то
отбрасывается условно левая половина оставшейся части массива.
Работа алгоритма продолжается до тех пор, пока не будет найдено нужное
критерию поиска значение.
Если целевого объекта нет в массиве поиск заканчивается неудачей.
Крючков А.В.
4

5.

Вопрос 1. Описание методов поиска.
1.1. Бинарный (двоичный) поиск
Для более быстрого поиска могут использоваться хэш-таблицы.
Существует множество вариаций двоичного поиска. Дробное
каскадирование используется при поиске одинаковых значений
одновременно в нескольких массивах. Использование данного
варианта метода существенно ускоряет его работу. Его используют
для решения задач поиска, например, в вычислительной геометрии.
Другой вариант двоичного поиска – экспоненциальный поиск.
Он использует метод двоичного поиска в списках неограниченной
длины.
Крючков А.В.
5

6.

Вопрос 1. Описание методов поиска.
1.1. Бинарный (двоичный) поиск
Алгоритм поиска состоит из следующих шагов:
1. Определяем верхнюю и нижнюю границы поиска.
2. Сравниваем их. Если они равны или нижняя граница больше верхней, завершаем
работу. Поиск неудачный. Если нет, то переходим к шагу 3.
3. Определяем положение «среднего» элемента с индексом, равным половине суммы
значений верхней и нижней границы.
4. Сравниваем значение данного элемента со значением критерия поиска. Если они
совпадают – элемент найден, поиск завершён удачно. Если нет, изменяем значения
верхней и нижней границы:
- если значение критерия поиска превышает значения «среднего» элемента, то нижняя
граница становится равной значению его индекса +1, а верхняя остаётся прежней;
- если значение критерия поиска меньше значения «среднего» элемента, то верхняя
граница становится равной значению его индекса -1, а нижняя остаётся прежней.
5. Переходим к шагу 1.
Крючков А.В.
6

7.

Вопрос 1. Описание методов поиска.
1.1. Бинарный (двоичный) поиск
Из алгоритма видно, что в лучшем случае двоичный поиск выполнит только
1 сравнение. В этом смысле бинарный или двоичный поиск можно
практически считать самым быстрым из всех существующих методов
поиска. Это особенно заметно на больших НД. На малых НД это уже не так
заметно.
В худшем и среднем случаях алгоритм этого метода выполняет
n*log2(n) сравнений, при n элементах в массиве.
Основным его недостатком является необходимость сортировать тот
массив, в котором он будет осуществляться. С учётом этого, если двоичный
поиск будет выполняться в неотсортированном массиве, необходимо будет
к log2(n) сравнений прибавить n*log2(n), n или log2(n) перестановок в
зависимости от метода сортировки.
Крючков А.В.
7

8.

Вопрос 1. Описание методов поиска.
1.1. Бинарный (двоичный) поиск
Для более сложных НД, чем числовой массив, двоичный поиск будет
работать только в том случае, если для них будет создан числовой
массив ключей элементов данных НД.
После создания массива ключей (индексов) его следует отсортировать
(упорядочить ключи по возрастанию). А затем в уже отсортированном
массиве ключей выполнять поиск.
Данные процедуры (создания файлов ключей и их упорядочение по
возрастанию) используются при работе с базами данных (БД).
Упорядоченные массивы ключей записей БД называют индексами БД.
Зачастую бинарный поиск называют логарифмическим.
Крючков А.В.
8

9.

Вопрос 1. Описание методов поиска.
1.2. Индексно-последовательный поиск
Индексно-последовательный поиск
может считаться вариантом бинарного
поиска. В процессе реализации данного
метода поиска создаются две таблицы:
- основная таблица, в которую
заносятся значения элементов массива
вместе с ключами, упорядоченных по
возрастанию (голубой);
- таблица индексов, в которую
заносятся ключи элементов, по
значениям индексов через
определенный интервал (зелёный).
Крючков А.В.
9

10.

Вопрос 1. Описание методов поиска.
1.2. Индексно-последовательный поиск
Алгоритм поиска состоит из следующих шагов:
0. Устанавливаем значение критерия поиска.
1. Создаём массив с ключами для искомого массива. Ключи будут использоваться
в основной таблице для «связи» с индексами элементов искомого массива, в
котором выполняется поиск.
2. Создаём основную таблицу со значениями элементов массива и
присвоенными ключами.
3. Сортируем её по значениям ключей.
4. Устанавливаем значение интервала индексов созданной таблицы и создаём
таблицу индексов.
5. Устанавливаем нижнюю и верхнюю границы поиска, равные значениям
индексов первого и последнего элементов таблицы индексов.
Крючков А.В.
10

11.

Вопрос 1. Описание методов поиска.
1.2. Индексно-последовательный поиск
Алгоритм поиска состоит из следующих шагов:
6. Выполняем последовательный поиск в таблице индексов в соответствии
со значением критерия поиска. При этом для сравнения со значением
критерия следует извлекать значение элемента массива из основной
таблицы в соответствии со значением ключа в таблице индексов.
7. Если значение ключа, меньше заданного в критерии, то сдвигается
нижняя граница поиска в таблице индексов. Если значение ключа в
таблице индексов больше заданного в критерии, то сдвигается верхняя
граница поиска.
8. Переходим к шагу 4.
9. Если искомый элемент найден, то процесс завершается успешно. Если
после сравнения всех элементов массива со значением критерия поиска
совпадений не обнаружено, процесс завершается безуспешно.
Крючков А.В.
11

12.

Вопрос 1. Описание методов поиска.
1.2. Индексно-последовательный поиск
«Сдвигание границ» поиска может означать
создание новой таблицы индексов с новыми
границами и новым интервалом между ключами.
Это индекс «второго уровня», используемый для
таблицы индексов первого уровня. Количество таких
уровней может быть любым.
При реализации данного метода поиска часть
элементов основной таблицы как бы
«отбрасываются» (выводятся за рамки процесса).
Крючков А.В.
12

13.

Вопрос 1. Описание методов поиска.
1.2. Индексно-последовательный поиск
Материалов по эффективности данного метода поиска недостаточно,
чтобы сделать однозначную оценку по количеству сравнений.
Вам следует сделать это самостоятельно в соответствии с темой
курсовой и лабораторной работ.
Но в худшем («безуспешном») случае (искомого значения в
элементах НД нет), количество сравнений будет, очевидно,
определяться глубиной уровней таблиц индексов и умножаться на
число элементов НД.
Крючков А.В.
13

14.

Вопрос 1. Описание методов поиска.
1.3. Двунаправленный поиск
Данный метод в основном используется для
графов или деревьев.
Дерево в программировании может
моделироваться либо в виде последовательности
списков, либо в виде последовательности
указателей.
Двунаправленный эвристический поиск – это
поиск в пространстве состояний, при проведении
которого процесс из некоторого состояния s
переходит в другое состояние t, совершая поиск
пути из s в t и из t в s одновременно.
Здесь s и t – состояния, зафиксированные в дереве
переходов.
Крючков А.В.
14

15.

Вопрос 1. Описание методов поиска.
1.3. Двунаправленный поиск
В процессе поиска в дереве находят
допустимый список узлов,
переходы через которые, позволят
пройти по графу из s к t. Для
деревьев, если нет обратного пути
из t в s, поиск выполняется только
«прямым» образом.
Для обратного поиска в этом случае необходимо иметь возможность
находить узлы, позволяющие двигаться по дереву из глубины вверх.
На рис. дан пример для одномерного массива. Для него реализация
метода основана на одновременном «движении» по массиву с начала и с
конца.
Крючков А.В.
15

16.

Вопрос 1. Описание методов поиска.
1.3. Двунаправленный поиск
Алгоритм поиска состоит из следующих шагов:
0. Устанавливаем значение критерия поиска.
1. Устанавливаем нижнюю и верхнюю границы поиска. Изначально они равны
значениям индексов первого и последнего элементов искомого массива, в
котором выполняется поиск.
2. В цикле проверяем очередные первый и последний элемент на соответствие
критерию поиска.
3. Если найдено совпадение со значением критерия поиска, завершаем работу.
Если нет – переходим к шагу 1, изменяя верхнюю и нижнюю границы поиска на 1.
4.. Если искомый элемент найден, то процесс завершается успешно. Если после
сравнения всех элементов массива со значением критерия поиска совпадений не
обнаружено, процесс завершается безуспешно.
Крючков А.В.
16

17.

Вопрос 1. Описание методов поиска.
1.3. Двунаправленный поиск
Число сравнений в худшем случае равно числу n
элементов массива.
В лучшем случае число сравнений равно 1.
В среднем случае – n/2.
Массив не обязательно должен быть отсортирован.
Крючков А.В.
17

18.

Вопрос 1. Описание методов поиска.
1.4. Поиск по Фибоначчи
Метод поиска следует выполнять в отсортированном массиве.
По сути это вариация метода бинарного поиска, одним изменением:
массив делится на две неравные части.
«Точка» разделения элементов массива (индекс элемента,
разделяющего массив на две части) определяется в соответствии с
последовательностью чисел Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
89 и т.д.
В нём очередные члены (числа) определяются как сумма двух
предыдущих членов ряда, кроме первого. Наибольшее число из
ряда Фибоначчи, меньшее n – размера массива – становится
номером индекса для точки разделения.
Крючков А.В.
18

19.

Вопрос 1. Описание методов поиска.
1.4. Поиск по Фибоначчи
Если массив содержит 13 элементов
(число из ряда Фибоначчи) или 12
элементов, то в качестве точки
разделения для него выбирается число
8 – наибольшее число из ряда
Фибоначчи, меньшее размера массива.
Дальнейшие действия аналогичны
действиям при бинарном поиске.
Если указанный в качестве точки элемент совпадает со значением критерия
поиска, работа алгоритма завершается. Если нет, определяется то, в какой из
частей массива нужно проводить дальнейший поиск. При превышении
значения критерия поиска значения элемента массива в точке разделения
выбирается условно правая сторона массива. В противном случае – условно
левая.
Крючков А.В.
19

20.

Вопрос 1. Описание методов поиска.
1.4. Поиск по Фибоначчи
Алгоритм поиска состоит из следующих шагов:
0. Сортируем массив (если он не отсортирован). Устанавливаем
значение критерия поиска.
1. Определяем верхнюю и нижнюю границы поиска. Нижняя граница
равна индексу первого элемента массива. Верхняя определяется
исходя из наибольшего числа из ряда Фибоначчи, меньшего размера
массива.
2. Массив условно делится на 2 части: между первым элементом и
верхней границей поиска; между увеличенной на 1 верхней
границей поиска и числом элементов массива.
Крючков А.В.
20

21.

Вопрос 1. Описание методов поиска.
1.4. Поиск по Фибоначчи
Алгоритм поиска состоит из следующих шагов:
3. Значение элемента с верхней границей поиска сравнивается со
значением критерия поиска. Если они равны – поиск удачный, завершаем
работу. Если или нижняя граница равна или больше верхней – поиск
неудачный, завершаем работу.
4. Если значение критерия поиска не совпадает со значением элемента
массива в точке разделения, то определяем какую часть массива следует
«отбросить». Если меньше – отбрасываем условно правую часть массива,
чтобы продолжить поиск в условно левой части. Если больше –
отбрасываем условно левую часть массива.
5. Выбираем оставшуюся часть массива и переходим к шагу 1.
Крючков А.В.
21

22.

Вопрос 1. Описание методов поиска.
1.4. Поиск по Фибоначчи
Число сравнений в худшем случае равно числу n
элементов массива.
В лучшем случае число сравнений равно 1.
В среднем случае – n/2.
Крючков А.В.
22

23.

Вопрос 1. Описание методов поиска.
1.5. Интерполяционный поиск
В математической области численного анализа ИНТЕРПОЛЯЦИЯ
– это тип оценки, метод построения (нахождения) новых точек
данных на основе диапазона дискретного набора известных
точек данных.
Интерполя́ция, интерполи́ рование (от лат. inter–polis –
«разглаженный, подновлённый, обновлённый;
преобразованный») –в вычислительной математике нахождение
неизвестных промежуточных значений некоторой функции, по
имеющемуся дискретному набору её известных значений.
Крючков А.В.
23

24.

Вопрос 1. Описание методов поиска.
1.5. Интерполяционный поиск
Данный вид поиска является также развитием метода
бинарного поиска. Поэтому он возможен только в
отсортированном массиве (или ином НД).
В основе данного метода поиска лежит операция
интерполирования, которая заключается в том, чтобы
найти промежуточное значение, приближающее нас на
каждой следующей итерации к значению критерия
поиска, по имеющимся известным значениям
элементов массива.
На каждом шаге алгоритма метода проводится определение области, в которой
его следует вести.
При этом область поиска по мере работы алгоритма уменьшается.
Крючков А.В.
24

25.

Вопрос 1. Описание методов поиска.
1.5. Интерполяционный поиск
Определение новых границ поиска – точки разделения массива –
выполняется по следующей формуле