Линейный поиск

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

Слово «последовательный» содержит в себе основную идею метода. Начиная с первого, все элементы массива последовательно просматриваются и сравниваются с искомым. Если на каком-то шаге текущий элемент окажется равным искомому, тогда элемент считается найденным, и в качестве результата возвращается номер этого элемента, либо другая информация о нем. (Далее, в качестве выходных данных будет выступать номер элемента). Иначе, следуют возвратить что-то, что может оповестить о его отсутствии в пройденной последовательности.

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

Код программы на C++:

 

#include <ctime>

int i, n;

int LineSearch(int A[], int key) //линейный поиск

{

for (i=0; i<n; i++)

if (A[i]==key) return i;

return -1;

}

 

void main() //главная функция

{

int key, A[1000];

srand(time(NULL));

cout<<"Размер массива > "; cin>>n;

cout<<"Искомый элемент > "; cin>>key;

cout<<"Исходный массив: ";

for (i=0; i<n; i++)

{

A[i]=rand()%10;

cout<<A[i]<<" ";

}

if (LineSearch(A, key)==-1) cout<<"\nЭлемент не найден";

else cout<<"\nНомер элемента: "<<LineSearch(A, key)+1;

}

 

Код программы на Pascal:

 

type Arr=array[1..1000] of integer;

var key, i, n: integer;

A: Arr;

 

function lineSearch(A: Arr; key: integer): integer; {линейный поиск}

begin

lineSearch:=-1;

for i:=1 to n do

if A[i]=key then

begin

lineSearch:=i;

exit;

end;

end;

 

begin {основной блок программы}

randomize;

write('Размер массива > '); readln(n);

write('Искомый элемент > '); read(key);

write('Исходный массив: ');

for i:=1 to n do

begin

A[i]:=random(10);

write(A[i],' ');

end;

writeln;

if (lineSearch(A, key)=-1) then write('Элемент не найден')

else write('Номер элемента: ', lineSearch(A, key));

end.

 

В лучшем случае, когда искомый элемент занимает первую позицию, алгоритм произведет всего одно сравнение, а в худшем n, где n — количество элементов в массиве. Худшему случаю соответствуют две ситуации: искомый элемент занимает последнюю позицию, или он вовсе отсутствует в массиве.

Алгоритм линейного поиска не часто используется на практике, поскольку принцип работы «в лоб» делает скорость решения им задачи очень низкой. Его применение оправдано на небольших и/или неотсортированных последовательностях, но когда последовательность состоит из большого числа элементов, и с ней предстоит работать не раз, тогда наиболее оптимальным решением оказывается предварительная сортировка этой последовательности с последующим применением двоичного или другого, отличного от линейного, алгоритма поиска.