Линейный поиск в C++




линейный поиск с++, линейный поиск c++, для начинающих, алгоритмы поиска с++, для чайников, последовательный поиск, брутфорс

100% программистов, во время обучения, рано или поздно столкнутся с необходимостью проверить наличие в массиве определённого значения. Существует несколько общеизвестных алгоритмов поиска в языках программирования. Сейчас мы рассмотрим самый простой из них (но далеко не самый эффективный) — линейный поиск либо последовательный поиск. За счет того, что поиск проводится путем полного последовательного перебора элементов массива и сравнения его значений с заданным ключом, скорость работы алгоритма достаточно низкая.

Рассказывать тут особо нечего — лучше сразу показать линейный поиск в работе. В ниже приведенном примере объявим массив на 50 элементов и заполним его используя генератор случайных чисел rand(). Предложим пользователю ввести искомое значение с клавиатуры и реализуем проверку на наличие этого значения в нашем массиве. Если значение будет найдено в каком-либо элементе массива — выведем на экран индекс этого элемента. Это классический пример. Тяжело и придумать что-то лучшее для демонстрации линейного поиска в C++.

Функция выполняющая линейный поиск определена в строках 62-70. Она возвращает в программу -1 в том случае, если значение, которое ищет пользователь, не будет найдено в массиве. Если же значение будет найдено — функция вернет индекс элемента массива, в котором это значение хранится.

Запускаем:

линейный поиск с++, линейный поиск c++, для начинающих, алгоритмы поиска с++, для чайников, последовательный поиск, брутфорс

В случае отсутствия значения в массиве:

линейный поиск с++, линейный поиск c++, для начинающих, алгоритмы поиска с++, для чайников, последовательный поиск, брутфорс

Посмотрев на первый снимок, вы сразу обратите внимание, что в ячейке с индексом 6 искомое значение найдено и программа завершает работу, хотя в ячейках 23 и 33 этого массива находятся такие же значения. Если вас это устраивает, то индекс первого найденного элемента и будет результатом работы программы. Иначе программу надо дорабатывать, чтобы найти и записать (например в отдельный массив) все индексы ячеек, хранящих искомое число (ключ).

Обычно линейный поиск применяется для одиночного поиска в небольшом массиве, который не отсортирован. В других случаях, лучше и эффективней сначала отсортировать массив и применять другие алгоритмы поиска. Например двоичный (бинарный) поиск либо другие.

Чтобы поддержать наш сайт — нажмите на копилку и выберите любой удобный способ.

Рассылка новых уроков по программированию:


Согласен получать уведомления от purecodecpp.com на мой e-mail

Дата
Страница
Линейный поиск в C++
Рейтинг
5

Линейный поиск в C++: 3 комментария

  1. Функция, проверяющая наличие элемента в массиве должна возвращать bool (true если элемент есть и false если его нет).
    Нет смысле возвращать значение элемента, т.к. у клиента (того, кто вызвал функцию) уже есть это значение — он ведь передал его во втором аргументе, зачем ему получать его назад?
    Возвращать -1 при отсутствии элемента еще более бессмысленно, представьте что я хочу проверить наличие значения -1 в массиве.

    1. Посмотрел невнимательно, каюсь ) — функция возвращает не значение, а индекс, поэтому проблем никаких нет, все верно )

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

Код размещайте в тегах: <pre class="lang:c++ decode:true ">YOUR CODE</pre>