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 в масиві.
подивився неуважно, каюсь ) – функція повертатися не значення, а індекс, тому проблем ніяких немає, все вірно )