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

Линейный поиск в C++: подробное руководство

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

Сегодня мы изучим самый простой для реализации алгоритм поиска (но и самый затратный по времени) — линейный поиск.

Как работает линейный поиск

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

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

Как создать линейный поиск

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

В строке 26 мы предлагаем пользователю с клавиатуры ввести ключ, а дальше мы проверим массив на наличие этого ключа. Если ключ совпал с какой-то ячейкой в массиве, то мы выведем индекс этой ячейки. Это типичный пример чтобы понять как работает алгоритм.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
  setlocale(LC_ALL, "rus");
  
  int ans[20]; // создали массив для записи всех индексов
  int h = 0;
  int arr[20]; // создали массив на 20 элементов
  int key; // создали переменную в которой будет находиться ключ

  srand ( time(NULL) );

  for (int i = 0; i < 20; i++) {
    arr[i] = 1 + rand() % 20; // заполняем случайными числами ячейки

    cout << arr[i] << " "; // выводим все ячейки массива

    if (i == 9) {
      cout << endl;
    }
  }

  cout << endl << endl << "Введите ключ : "; cin >> key; // считываем ключ

  for (int i = 0; i < 20; i++) {
    if (arr[i] == key) { // проверяем равен ли arr[i] ключу
      ans[h++] = i;
    }
  }

  if (h != 0) { // проверяем были ли совпадения
    for (int i = 0; i < h; i++) {
      cout << "Ключ " << key << " находится в ячейке " << ans[i] << endl; //выводим все индексы
    }
  }
  else {
    cout << "Мы не нашли ключ " << key << " в массиве";
  }
  
  system("pause");
  return 0;
}

#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

int main() {

setlocale(LC_ALL, "rus");

int ans[20]; // создали массив для записи всех индексов

int h = 0;

int arr[20]; // создали массив на 20 элементов

int key; // создали переменную в которой будет находиться ключ

srand ( time(NULL) );

for (int i = 0; i < 20; i++) {

arr[i] = 1 + rand() % 20; // заполняем случайными числами ячейки

cout << arr[i] << " "; // выводим все ячейки массива

if (i == 9) {

cout << endl;

}

cout << endl << endl << "Введите ключ : "; cin >> key; // считываем ключ

for (int i = 0; i < 20; i++) {

if (arr[i] == key) { // проверяем равен ли arr[i] ключу

ans[h++] = i;

}

if (h != 0) { // проверяем были ли совпадения

for (int i = 0; i < h; i++) {

cout << "Ключ " << key << " находится в ячейке " << ans[i] << endl; //выводим все индексы

}

else {

cout << "Мы не нашли ключ " << key << " в массиве";

}

system("pause");

return 0;

}

Линейный поиск находится в строках 28 — 32.

Давайте разберем этот пример:

В строке 9 — 10: мы создали массив ans и переменную h (равную нулю).

В массиве ans будут храниться все индексы.

В строке 29: мы применили оператор ветвления if.
- Если результат условия положительный, то в ячейку ans[h] присваиваем значение i, а переменную h увеличиваем на один.

В строке 34: проверяем:
- Если результат условия положителен, то выводим h первых элементов массива ans;
- Если же результат условия отрицателен, то выводим «Мы не нашли ключ key в массиве»

Давайте выполним этот код:

line_search.cpp

2 8 15 1 10 5 19 19 3 5

6 6 2 8 2 12 16 3 8 17

Введите ключ : 8

Ключ 8 находится в ячейке 1

Ключ 8 находится в ячейке 13

Ключ 8 находится в ячейке 18

Process returned 0 (0x0) execution time : 0.020 s

Press any key to continue.

А если такого ключа нет в массиве :

line_search.cpp

19 1 14 9 2 12 6 14 8 2

11 16 3 4 2 16 19 14 7 15

Введите ключ : 5

Мы не нашли ключ 5 в массиве

Process returned 0 (0x0) execution time : 0.020 s

Press any key to continue.

Использовать ли линейный поиск

Из плюсов у этого алгоритма только одно — простая реализация.

Минус один, но очень большой — код работает медленно.

Мы советуем использовать его «чайникам» для решения их первых задач. Однако, если вы разрабатываете высоко нагруженное приложение или веб-сервер, такой поиск будет слишком затратным. Вам понадобятся более эффективные алгоритмы. Например, бинарный поиск. Он работает очень быстро и реализация не на много сложнее линейного поиска.

Упражнение

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

Если вы будете использовать функцию rand для заполнения массива случайными числами, то чтобы после первого запуска программы случайные числа не повторялись, используйте функцию srand ( time(NULL) ), перед тем как используете функцию rand.

Надеемся, что эта статья помогла вам узнать, что такое линейный поиск и как он работает. Если вы нашли ошибки в статье или хотите задать вопрос, то пишите в комментарии. Удачи!

« Бинарный поиск в C++

Массив в C++ »

26 января 2017

Алгоритмы

Комментарии

Комментарии к записи “Линейный поиск в C++: подробное руководство”

Добавить комментарий Отменить ответ

Vlad:

25.04.2017 в 06:41

Здравствуйте, я хотел бы разобраться в следующей строчке кода: if (arr[i] == key) {
ans[h++] = i; }. Мне не понятно , как работает вот эта часть кода: ans[h++] = i.

Ответить
- Дмитрий:
  
  25.04.2017 в 14:02
  
  Это стандартный прием в C++. Мы используем постфиксный инкремент. Сначала мы получаем доступ к элементу массива, а только потом переменная h увеличивается на 1. Если вы хотите подробнее узнать про это, можете почитать эту статью: https://codelessons.ru/cplusplus/syntax/inkrement-i-dekrement-v-c.html
  
  Ответить
Сергей:

22.09.2018 в 21:54

А как сделать поиск последовательности элементов? Например, пользователь ввёл 2 и 8 и нужно вывести где есть такое совпадение?
В вашем примере ответ был бы:
Ключ 2 8 находится в ячейке 1
Ключ 2 8 находится в ячейке 12

Ответить

Vlad:

25.04.2017 в 06:41

Здравствуйте, я хотел бы разобраться в следующей строчке кода: if (arr[i] == key) {
ans[h++] = i; }. Мне не понятно , как работает вот эта часть кода: ans[h++] = i.

Ответить

Дмитрий:

25.04.2017 в 14:02

Это стандартный прием в C++. Мы используем постфиксный инкремент. Сначала мы получаем доступ к элементу массива, а только потом переменная h увеличивается на 1. Если вы хотите подробнее узнать про это, можете почитать эту статью: https://codelessons.ru/cplusplus/syntax/inkrement-i-dekrement-v-c.html

Ответить

Сергей:

22.09.2018 в 21:54

А как сделать поиск последовательности элементов? Например, пользователь ввёл 2 и 8 и нужно вывести где есть такое совпадение?
В вашем примере ответ был бы:
Ключ 2 8 находится в ячейке 1
Ключ 2 8 находится в ячейке 12