Задача поиска заключается в отыскании в заданной последовательности элемента или нескольких элементов с заданными свойствами.

Существует несколько основных вариантов организации поиска данных:

1. Поиск номера элемента последовательности с заданным значением.


2. Поиск максимального или минимального элемента и его номера в заданной последовательности.

Задачу А можно назвать основной задачей, а задачу В – производной от А.

Последовательность для поиска может быть как упорядоченная, так и неупорядоченная.

Примем следующее допущение.

Пусть задана определенная последовательность данных {Xi} = X1, X2,…,XN, где I изменяется от 1 до N, длина N которой является фиксированной величиной. Все элементы имеют разные значения. Необходимо найти некоторый заданный элемент.

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

Поиск номера элемента последовательности с заданным значением.

По условию поиска для некоторой исходной последовательности необходимо определить номер элемента, значение которого равно значению заданной переменной Р.

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

Особенностями такого поиска являются:

• независимость поиска


• цикличность поиска – количество повторений не превышает количество элементов в заданной последовательности


• простота реализации алгоритма.

Условиями окончания процесса поиска являются:

• элемент найден, т.е. Р = Xi


• элемент не найден, хотя массив просмотрен от начала до конца, но при этом совпадений не было.

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

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

Основной алгоритм поиска будет следующим:

1. сравнить очередной элемент с переменной Р.


2. перейти к следующему элементу.


3. если не все элементы просмотрены, повторить, начиная с п. 1.

Алгоритм должен однозначно реагировать на ситуацию, если искомого значения в последовательности нет. Для этой цели вводится в алгоритм переменная k, начальное значение которой равно 0. Результат k>0 – номер найденного элемента. Если элемент со значением Р не найден, то результат k остается нулевым.

Эффективность поиска прямо пропорциональна количеству вычислений.