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

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

Для начала, мы рассмотрим наиболее простой из способов поиска данных - линейный поиск.

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

#include <iostream> using namespace std; int LinearSearch (int array[], int size, int key){ for(int i=0;i<size;i++) if(array[i] == key) return i; return -1; } void main() { const int arraySize=100; int a[arraySize], searchKey, element; for(int x=0;x<arraySize;x++) a[x]=2*x; //Следующая строка выводит на экран сообщение //Введите ключ поиска: cout<<"Please, enter the key: "; cin>>searchKey; element=LinearSearch(a, arraySize, searchKey); if(element!=-1) //Следующая строка выводит на экран сообщение //Найдено значение в элементе cout<<"\nThe key was found in element "<<element<<'\n'; //Следующая строка выводит на экран сообщение //Значение не найдено else cout<<"\nValue not found "; }

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