Основи програмування на С ++ для початківців

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

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

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

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

Запускаем:

лінійний пошук з ++, лінійний пошук c ++, для початківців, алгоритми пошуку з ++, для чайників, послідовний пошук, ʙrutfors

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

лінійний пошук з ++, лінійний пошук c ++, для початківців, алгоритми пошуку з ++, для чайників, послідовний пошук, ʙrutfors

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

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

3 думки про "Линейный поиск в C

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

залишити коментар

Ваша електронна адреса не буде опублікований. Обов'язкові поля позначені * *