Поиск элемента в массиве

Пожалуй, наиболее важной задачей, связанной с массивами, является поиск элемента в массиве. Есть ли интересующий нас товар в магазине? Включены ли вы в число студентов, получивших президентскую стипендию? Как переводится какое-то слово на русский язык? Все эти вопросы сводятся к задаче поиска элемента в массиве, который может быть перечнем товаров, списком студентов или слов в словаре.

Существует масса модификаций данной задачи, поэтому мы рассмотрим базовый алгоритм, который используется практически во всех модификациях. Суть задачи заключается в том, что по заданному элементу требуется проверить, есть ли он в массиве или нет. Существует очень распространенное ошибочное решение этой задачи, поэтому начнем с его рассмотрения.

int x = 50;

for (int i=0; i<size; i++) {

if (x == numbers[i]) {

cout << "Такой элемент есть в массиве\n";

} else {

cout << "Такого элемента нет в массиве\n";

}

}

В данной реализации несколько ошибок. Подумайте, какие? Рассмотрим одну из них. Предположим, что элемента в массиве нет, тогда на каждой итерации цикла будет выполняться ветка else, и на экране появятся size сообщений о том, что элемента нет. Если же искомый элемент находится где-то в середине, что программа вначале выведет несколько сообщений об отсутствии, затем – одно сообщение о том, что элемент найден, а затем опять начнет сообщать, что элемента нет.

Что же делать? Нужно заметить два аспекта:

• если элемент найден, то поиск можно заканчивать;
• убедиться в отсутствии элемента можно лишь, пройдя весь массив.

Следующая программа учитывает эти аспекты:

//Искомый элемент

int x = 50;

//Нашли или нет

bool found = false;

for (int i=0; i<size; i++) {

if (x == numbers[i]) {

//Отмечаем, что элемент найден

found = true;

//Заканчиваем чикл

break;

}

}

//found эквивалентно found==true

if (found) {

cout << "Такой элемент есть в массиве\n";

} else {

cout << "Такого элемента нет в массиве\n";

}