2014-02-18
246Поиск элемента в массиве
Пожалуй, наиболее важной задачей, связанной с массивами, является поиск элемента в массиве. Есть ли интересующий нас товар в магазине? Включены ли вы в число студентов, получивших президентскую стипендию? Как переводится какое-то слово на русский язык? Все эти вопросы сводятся к задаче поиска элемента в массиве, который может быть перечнем товаров, списком студентов или слов в словаре.
Существует масса модификаций данной задачи, поэтому мы рассмотрим базовый алгоритм, который используется практически во всех модификациях. Суть задачи заключается в том, что по заданному элементу требуется проверить, есть ли он в массиве или нет. Существует очень распространенное ошибочное решение этой задачи, поэтому начнем с его рассмотрения.
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";
}
Задача поиска «самого-самого» всегда актуальна. Кто из футболистов забил больше всего голов? У кого самая большая зарплата? Кто имеет максимальный рейтинг? Подобные вопросы возникают повсюду, но далеко не все представляют себе алгоритм нахождения этих «звезд». Мы изучим этот алгоритм на примере поиска максимального элемента в целочисленном массиве, а распространить его на перечисленные выше задачи не составит труда.
Для поиска максимального элемента в массиве существует стандартный алгоритм, который заключается в том, что заводится переменная (назовем ее 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 <clocale>
#include <iostream>
using namespace std;
#define 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;
}
Если требуется найти не максимальный элемент, а его индекс, то программа несколько изменится:
int ind_max = 0;
for (int i=1; i<size; i++) {
if (numbers[ind_max] < numbers[i]) {
ind_max = i;
}
}
