Поиск

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

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

#include <iostream.h >

int LinearSearch(int [], int, int);

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 ";
}

int LinearSearch (int array[], int size, int key)
{
 for (int i = 0; i < size; i++)
 if(array[i] == key)
 return i;
 return -1;
}

Метод линейного поиска хорошо работает для небольших или для несортированных массивов. И хотя для больших массивов линейный поиска неэффективен, лмнейный поиск абсолютно надежен.