Для нахождения некоторого элемента (ключа) в заданном неупорядоченном массиве используется алгоритм линейного (последовательного) поиска. Он работает как с неотсортированными массивами, так и отсортированными, но для вторых существуют алгоритмы эффективнее линейного поиска.
Эту неэффективность компенсируют простая реализация алгоритма и сама возможность применять его к неупорядоченным последовательностям. Здесь, а также при рассмотрении всех других алгоритмов поиска, будем полагать, что в качестве ключа выступает некоторая величина, по мере выполнения алгоритма, сравниваемая именно со значениями элементов массива.
Алгоритм линейного поиска
Слово «последовательный» содержит в себе основную идею метода. Начиная с первого, все элементы массива последовательно просматриваются и сравниваются с искомым. Если на каком-то шаге текущий элемент окажется равным искомому, тогда элемент считается найденным, и в качестве результата возвращается номер этого элемента, либо другая информация о нем. (Далее, в качестве выходных данных будет выступать номер элемента). Иначе, следуют возвратить что-то, что может оповестить о его отсутствии в пройденной последовательности.
Ниже, на примере фигур, наглядно демонстрируется работа алгоритма линейного поиска. В качестве искомого элемента (в данном случае это квадрат) задается фигура, и она поочередно сравнивается со всеми имеющимися фигурами до тех пор, пока не будет найдена тождественная ей фигура, или окажется, что в данном множестве таковой нет.
Примечателен тот факт, что имеется вероятность наличия нескольких элементов с одинаковыми значениями, совпадающими со значением ключа. В таком случае, если нет конкретных условий, можно, например, за результирующий взять номер первого найденного элемента (реализовано в листинге ниже), или записать в массив номера всех тождественных элементов.
Код программы на C++:
#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;
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()
{
setlocale(LC_ALL,"Rus");
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;
system("pause>>void");
}
Код программы на Pascal:
program linearSearch;
uses crt;
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 — количество элементов в массиве. Худшему случаю соответствуют две ситуации: искомый элемент занимает последнюю позицию, или он вовсе отсутствует в массиве.
Алгоритм линейного поиска не часто используется на практике, поскольку принцип работы «в лоб» делает скорость решения им задачи очень низкой. Его применение оправдано на небольших и/или неотсортированных последовательностях, но когда последовательность состоит из большого числа элементов, и с ней предстоит работать не раз, тогда наиболее оптимальным решением оказывается предварительная сортировка этой последовательности с последующим применением двоичного или другого, отличного от линейного, алгоритма поиска.