100% программистов, во время обучения, рано или поздно столкнутся с необходимостью проверить наличие в массиве определённого значения. Существует несколько общеизвестных алгоритмов поиска в языках программирования. Сейчас мы рассмотрим самый простой из них (но далеко не самый эффективный) – линейный поиск либо последовательный поиск. За счет того, что поиск проводится путем полного последовательного перебора элементов массива и сравнения его значений с заданным ключом, скорость работы алгоритма достаточно низкая.
Рассказывать тут особо нечего – лучше сразу показать линейный поиск в работе. В ниже приведенном примере объявим массив на 50 элементов и заполним его используя генератор случайных чисел rand(). Предложим пользователю ввести искомое значение с клавиатуры и реализуем проверку на наличие этого значения в нашем массиве. Если значение будет найдено в каком-либо элементе массива – выведем на экран индекс этого элемента. Это классический пример. Тяжело и придумать что-то лучшее для демонстрации линейного поиска в C++.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include <iostream> #include <iomanip> #include <ctime> using namespace std; //прототипы функций int linSearch(int arr[], int requiredKey, int size); // линейный поиск void showArr(int arr[], int size); // показ массива int main() { setlocale(LC_ALL, "rus"); const int arrSize = 50; int arr[arrSize]; int requiredKey = 0; // искомое значение (ключ) int nElement = 0; // номер элемента массива srand(time(NULL)); //запись случ. чисел в массив от 1 до 50 for (int i = 0; i < arrSize; i++) { arr[i] = 1 + rand() % 50; } showArr(arr, arrSize); cout << "Какое число необходимо искать? "; cin >> requiredKey; // ввод искомого числа //поиск искомого числа и запись номера элемента nElement = linSearch(arr, requiredKey, arrSize); if (nElement != -1) { //если в массиве найдено искомое число - выводим индекс элемента на экран cout << "Значение " << requiredKey << " находится в ячейке с индексом: " << nElement << endl; } else { //если в массиве не найдено искомое число cout << "В массиве нет такого значения" << endl; } return 0; } //вывод массива на экран void showArr(int arr[], int arrSize) { for (int i = 0; i < arrSize; i++) { cout << setw(4) << arr[i]; if ((i + 1) % 10 == 0) { cout << endl; } } cout << endl << endl; } //линейный поиск int linSearch(int arr[], int requiredKey, int arrSize) { for (int i = 0; i < arrSize; i++) { if (arr[i] == requiredKey) return i; } return -1; } |
Функция выполняющая линейный поиск определена в строках 62-70. Она возвращает в программу -1 в том случае, если значение, которое ищет пользователь, не будет найдено в массиве. Если же значение будет найдено – функция вернет индекс элемента массива, в котором это значение хранится.
Запускаем:
В случае отсутствия значения в массиве:
Посмотрев на первый снимок, вы сразу обратите внимание, что в ячейке с индексом 6 искомое значение найдено и программа завершает работу, хотя в ячейках 23 и 33 этого массива находятся такие же значения. Если вас это устраивает, то индекс первого найденного элемента и будет результатом работы программы. Иначе программу надо дорабатывать, чтобы найти и записать (например в отдельный массив) все индексы ячеек, хранящих искомое число (ключ).
Обычно линейный поиск применяется для одиночного поиска в небольшом массиве, который не отсортирован. В других случаях, лучше и эффективней сначала отсортировать массив и применять другие алгоритмы поиска. Например двоичный (бинарный) поиск либо другие.
Функция, проверяющая наличие элемента в массиве должна возвращать bool (true если элемент есть и false если его нет).
Нет смысле возвращать значение элемента, т.к. у клиента (того, кто вызвал функцию) уже есть это значение – он ведь передал его во втором аргументе, зачем ему получать его назад?
Возвращать -1 при отсутствии элемента еще более бессмысленно, представьте что я хочу проверить наличие значения -1 в массиве.
Посмотрел невнимательно, каюсь ) – функция возвращает не значение, а индекс, поэтому проблем никаких нет, все верно )