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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. В строке 29: мы применили оператор ветвления if.
    • Если результат условия положительный, то в ячейку ans[h] присваиваем значение i, а переменную h увеличиваем на один.
  1. В строке 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++: подробное руководство”

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

  • Vlad:

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

    • Дмитрий:

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

  • Сергей:

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