Методы поиска в массиве данных

1. Последовательный поиск
Дана последовательность записей
R1, R2, …, RN
с ключами k1, k2, …, kN.
Алгоритм предназначен для поиска элемента последовательности с заданным ключом k при N 1

Блок-схема алгоритма 1

2. Быстрый последовательный поиск
В отличие от предыдущего алгоритма здесь предполагается, что в конце последовательности имеется фиктивный элемент RN+1, равный искомому ключу k

Блок-схема алгоритма 2
k = ki
i++
удача
неудача
i = 1
kN+1 = k
да
нет
нет
да

3. Бинарный (дихотомический) поиск
С помощью данного алгоритма разыскивается элемент последовательности записей
R1, R2, …, RN,
ключи которых расположены в возрастающем порядке:
k1< k2 < … < kN

Блок-схема алгоритма 3

Пример бинарного поиска
Дана последовательность из 9 элементов:
5, 4, 8, 1, 3, 7, 2, 9, 10
необходимо найти элемент, равный 7.
Решение: 1. Упорядочить по возрастанию исходную последовательность.
1, 2, 3, 4, 5, 7, 8, 9, 10
2. Найти средний элемент путем деления нацело общего числа элементов.
9div2=4, ki=4, k=7.
3. Поскольку k>ki, то дальнейший путь поиска вычисляется следующим образом: