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

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

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

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";

}

2.4.8Нахождение максимального элемента в массиве

Задача поиска «самого-самого» всегда актуальна. Кто из футболистов забил больше всего голов? У кого самая большая зарплата? Кто имеет максимальный рейтинг? Подобные вопросы возникают повсюду, но далеко не все представляют себе алгоритм нахождения этих «звезд». Мы изучим этот алгоритм на примере поиска максимального элемента в целочисленном массиве, а распространить его на перечисленные выше задачи не составит труда.

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

int max = numbers[0];

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

if (max < numbers[i]) {

max = numbers[i];

}

}

Часто переменную max инициализируют некоторым «очень маленьким числом», а цикл начинают не с 1, а с 0. Подобный алгоритм выглядит так:

int max = -1000000;

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

if (max < numbers[i]) {

max = numbers[i];

}

}

Однако данный подход нежелателен, поскольку нет гарантии, что число меньше «очень маленького числа» не встретится. Полный код поиска максимума выглядит так:

#include <iostream>

using namespace std;

const int MAX_SIZE = 100;

int main() {

setlocale(LC_ALL, "Russian");

int numbers[MAX_SIZE];

cout << "Введите размер массива: ";

int size;

cin >> size;

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

numbers[i] = rand()%100;

}

cout << "Задан следующий массив:\n";

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

cout << numbers[i] << " ";

}

cout << endl;

int max = numbers[0];

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

if (max < numbers[i]) {

max=numbers[i];

}

}

cout << "Макс. элемент = " << max << endl;

system("pause");

return 0;

}