Основы программирования на С++ для начинающих

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

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

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

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

Запускаем:

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

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

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

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

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

3 thoughts on “Линейный поиск в C++

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

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

Добавить комментарий для Programmer_blog Отменить ответ

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