1. Алгоритм линейного поиска

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

Уточненный алгоритм будет таким.

1. Ввести исходный массив (ключей).

2. Выполнять

2. 1. Ввести аргумент поиска (целое число);

2. 2. Если аргумент поиска больше или равен нулю,

1. Результат (номер в массиве, num) = - 1 (не найден, такого номера нет);

2. Для индекса массива (i) от 0 до Длина.массива

Если аргумент поиска = ключ[i],

номер в массиве (num) = i;

3. Если номер num = - 1,

вывести: «Такого ключа в массиве нет»,

Иначе

вывести: «Ключ найден под номером num».

пока будет аргумент поиска больше или равен нулю.

3. Закончить.

Основной недостаток алгоритма линейного поиска – большое время. Он предполагает использование оператора For в пункте 2.2.2. При этом ВСЕГДА выполняется ровно n операций сравнения, не зависимо от того, найден ключ или нет. Программа, обнаружив аргумент в начале массива, продолжает его просмотр до конца, т.е. выполняет бесполезную работу. Время поиска может быть существенно сокращено, если обеспечить его прекращение, когда ключ найден. При равномерном распределении элементов в таблице эталонов (ключей) среднее время поиска может стать пропорциональным величине n / 2.

Этого можно достичь, изменив пункт 2.2 в рассмотренном выше алгоритме следующим образом.

Ускорение линейного поиска

2. Выполнять

2. 1. Ввести аргумент поиска (целое число);

2. 2. Если аргумент поиска больше или равен нулю,

1. Результат (num) = - 1 (не найден);

2. Начальный индекс, i=0;

2.2.3. Пока (num=-1) и (i<=n – Длины.массива)

1. Если аргумент поиска = ключ[i],

номер в массиве (num) = i;

2. i=i + 1

4. Если номер num = - 1,

вывести: «Такого ключа в массиве нет»,

Иначе

вывести: «Ключ num найден».

пока будет аргумент поиска больше или равен нулю.

Трудоемкость (временная сложность) алгоритма линейного поиска определяется числом операций сравнения, выполняемых при просмотре таблицы эталонов. В лучшем случае количество таких операций равно 1, в худшем – n, а в среднем, если возможные значения ключей равновероятны, - n / 2. Таким образом, асимптотическая оценка О(n) = n.

2. Алгоритм дихотомического поиска

Этот алгоритм является более быстрым, чем линейный, но применяется только к упорядоченным массивам. Среднее время дихотомического поиска пропорционально величине log₂n, где n — количество элементов таблицы эталонов. Таким образом, ускорение достигается за счет дополнительной информации о расположении элементов, а асимптотическая оценка алгоритма О(n) = log₂n.

Метод основан на последовательном делении на 2 диапазона поиска. При этом на каждом шаге либо находится элемент, либо происходит переход в одну из половин диапазона. В процессе поиска выполняется не только сравнение на равенство, но и на больше - меньше. Последняя операция позволяет выбрать очередную половину диапазона таблицы. Если массив эталонов не упорядочен, то выбор будет сделан неверно, и результат можно не получить никогда (говорят, что алгоритм расходится).

Общий алгоритм поиска будет таким же, как в п. 1.

1. Ввести исходный массив (ключей).

2. Повторять

ввести аргумент поиска и вывести результат

пока не надоест.

3. Закончить.

Для корректности работы алгоритма необходимо упорядочить ключи (массив эталонов) по возрастанию. Для простоты их значения можно задать с помощью датчика случайных чисел. После этого необходимо выполнить операцию сортировки полученных величин.

Уточненный алгоритм можно представить в следующем виде.

1. Ввести количество элементов массива (n).

2. Инициировать датчик случайных чисел.

3. Для номера элемента (i) от 0 до n

1.3.1. Вычислить ключ[i].

2. Упорядочить ключи по возрастанию:

2.1. Для номера просмотра (k) от 1 до n - 1

2.1.1. Для номера слова (i) от 0 до n - k

Если ключ [i] > ключ [i+1],

поменять местами ключ[i] и ключ[i+1].

3. Выполнять

3. 1. Ввести аргумент поиска (целое число);

3. 2. Если аргумент поиска больше или равен нулю,

3.2.1 Граница_левая (диапазона поиска) = 0;

3.2.2. Граница_правая (диапазона поиска) = n - 1 (Длина.массива – 1);

3.2.3. Если аргумент поиска = ключ [n - 1],

1. Признак = «Найдено»;

2. k = n – 1.

Иначе

3.2.4. Признак = «Не найдено».

3.2.5. Выполнять

a) Номер аргумент поиска (k) = Целое ((Граница_левая + Граница_правая)/2);

b) Если аргумент поиска = ключ [k],

Признак:= «Найдено»

Иначе

Если аргумент поиска > ключ [k],

Граница_левая = k

Иначе

Граница_правая = k.

Пока не «Найдено» Или (Граница_левая = Граница_правая - 1).

3.3. Если «Найдено»,

вывести: «Ключ найден под номером k»,

Иначе

вывести: «Такого ключа в массиве нет».

Пока будет аргумент поиска больше или равен нулю.

4. Закончить.

В алгоритме пункт 3.2.3 применен для обеспечения нахождения последнего элемента массива. Дело в том, что при целочисленном делении на 2 дробная часть частного отбрасывается, и результат всегда будет на 1 меньше, чем длина таблицы.