Линейный поиск в C++ для начинающих

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

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

#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;
}

#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 этого массива находятся такие же значения. Если вас это устраивает, то индекс первого найденного элемента и будет результатом работы программы. Иначе программу надо дорабатывать, чтобы найти и записать (например в отдельный массив) все индексы ячеек, хранящих искомое число (ключ).

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

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

Programmer_blog:
05.05.2015 в 04:44
Функция, проверяющая наличие элемента в массиве должна возвращать bool (true если элемент есть и false если его нет).
Нет смысле возвращать значение элемента, т.к. у клиента (того, кто вызвал функцию) уже есть это значение – он ведь передал его во втором аргументе, зачем ему получать его назад?
Возвращать -1 при отсутствии элемента еще более бессмысленно, представьте что я хочу проверить наличие значения -1 в массиве.
Ответить
1. Programmer_blog:
  05.05.2015 в 04:45
  Посмотрел невнимательно, каюсь ) – функция возвращает не значение, а индекс, поэтому проблем никаких нет, все верно )
  Ответить
Уведомление: Двоичный (бинарный) поиск в С++ | PureCodeCpp

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

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

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

Свежие записи

Свежие комментарии

Статистика