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

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

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

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

//подключаем заголовочные файлы
#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <time.h>

//прототипы функций
int linearSearch(int[], int, int);
void printArray(int[], int);

//подключаем простронство имен std
using namespace std;

//главная функция программы
int main()
{

    const int arraySize = 100;
    int a[arraySize], searchKey, element;
    srand(time(NULL));

    //наполняем массив случайными числами в интервале от 0 до 100
    for (int i = 1; i <= arraySize; i++)

        a[i] = rand() % 100;

    //запрашиваем у пользователя ключ поиска (целое число)
    cout << "Enter a key of search: " << endl;
    cin >> searchKey;

    //выводим на экран наш массив
    printArray(a, arraySize);

    //выполняем поиск, путем вызова функции поиска
    element = linearSearch(a, searchKey, arraySize);

    if (element != -1)

        //если значение найдено в массиве, то выводим его индекс
        cout << "Value is found in an element " << element << endl;

    else

        //значение не найдено - выводим сообщение
        cout << "Value is not found" << endl;

    return 0;

}

//функция для вывода массива на экран
void printArray(int array[], int size)
{

    for (int i = 1; i <= size; i++)
    {

        cout << setw(4) << array[i];

        if (i % 10 == 0)

            cout << endl;

    }

    cout << endl << endl;

}

//функция, выполняющая линейный поиск в массиве
int linearSearch(int array[], int key, int sizeOfarray)
{

    for (int i = 1; i <= sizeOfarray; i++)
    {

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

    }

    return -1;

}

Результат работы программы линейного поиска:

Также можно использовать для поиска рекурсивный вариант линейного поиска в массиве:

//Линейный поиск (рекурсия)

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <time.h>

void print (int[], int);
int linearSearch (int[], int, int);
using namespace std;

int main()
{

    const int size = 100;
    int array[size];
    int key, value;

    srand (time(NULL));

    for (int i = 1; i <= size; i++)

        array[i] = rand() % 100;

    cout << "Enter a key of search: ";
    cin >> key;

    print (array, size);
    value = linearSearch (array, size, key);

    if (value != -1)

        cout << "Value is found in an element " << value << endl;

    else

        cout << "Value is not found" << endl;

    return 0;

}

int linearSearch (int a[], int arraySize, int keyOfSearch)
{

    static int index = 1;

    if (index <= arraySize)
    {

        if (a[index] == keyOfSearch)

            return index;

        else
        {

            index++;
            return linearSearch (a, arraySize, keyOfSearch);

        }

    }
    else

        return -1;

}

void print (int arr[], int sizeOfArray)
{

    cout << endl;

    for (int i = 1; i <= sizeOfArray; i++)
    {

        cout << setw(3) << arr[i];

        if (i % 10 == 0)

            cout << endl;

    }

    cout << endl;

}

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