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

обложка статьи

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

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

Интересное
Последние новости в мире программирования
Самые свежие новости и полезные материалы в моем telegram канале.
go

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

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

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

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

Давайте посмотрим как работает линейный поиск на практике.В примере ниже мы создали массив на 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;
}

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

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

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

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

  1. В строке 29: мы применили оператор ветвления if.

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

  2. В строке 34: проверяем:

    • Если результат условия положителен, то выводим h первых элементов массива ans;
    • Если же результат условия отрицателен, то выводим “Мы не нашли ключ key в массиве”

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

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.

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

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.

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

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

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

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

Интересное
Последние новости в мире программирования
Самые свежие новости и полезные материалы в моем telegram канале.
go

Упражнение

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

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

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

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

Массив в C++ »

Если хотите всегда быть в курсе последних новостей в мире программирования и IT, подписываетесь на мой Telegram-канал, где я делюсь свежими статьями, новостями и полезными советами. Буду рад видеть вас среди подписчиков!

Массивы в C++
В данном уроке мы научимся работать с массивами. Массивы являются самым популярным способом хранения больших объемов данных. Поэтому давайте разбираться!
go
Map в C++
В данном уроке вы узнаете: что такое map, как правильно его использовать, какими функциями можно оперировать, а также стоит ли его использовать у себя в проектах.
go
Функция map::find в C++
Ключевой функцией std::map в C++ является map::find, которая необходима для быстрого поиска элементов. В этой статье мы рассмотрим назначение этой функции, изучим ее механику и приведем практический пример."
go
Динамические массивы и переменные в C++
Как пользоваться динамическими переменными и массивами в C++. Мы разберем как их создать и узнаем их плюсы перед использованием обычных массивов.
go
Функция find в C++
Разберемся в функции find из C++ и научимся использовать ее с такими контейнерами, как vector и set.
go
Функция rand в C++
Язык C++ имеет несколько способов генерации случайных чисел. Функция rand - один из самых популярных способов получить случайное число. В этой статье мы научимся использовать эту функцию, генерировать случайные числа в диапазоне, а также реализуем свой простенький генератор случайных чисел.
go
Set и multiset в C++
В данном уроке вы познакомитесь с двумя контейнерами C++, которые очень важны - set и multiset. По другому их еще называют множеством и мультимножеством. Они автоматически сортируются при добавлении нового элемента. Но у каждого из них есть своя особенность, которую мы разбираем в этой статье.
go
Векторы в C++
В этом уроке вы узнаете, что такое вектор в C++, а также если вы хотите узнать, как правильно пользоваться и какие функции к им применять - то вам сюда.
go
Оператор ветвления
В данной статье мы подробно разберем условные операторы if и else. Мы создадим простую программу, которая будет использовать конструкцию ветвления в C++.
go

Обсуждение

Содержание
Подпишись на мой Telegram-канал
Получай последние новости о технологиях и программировании!