2015-07-14
309
Пожалуй, наиболее важной задачей, связанной с массивами, является поиск элемента в массиве. Есть ли интересующий нас товар в магазине? Включены ли вы в число студентов, получивших президентскую стипендию? Как переводится какое-то слово на русский язык? Все эти вопросы сводятся к задаче поиска элемента в массиве, который может быть перечнем товаров, списком студентов или слов в словаре.
Существует масса модификаций данной задачи, поэтому мы рассмотрим базовый алгоритм, который используется практически во всех модификациях. Суть задачи заключается в том, что по заданному элементу требуется проверить, есть ли он в массиве или нет. Существует очень распространенное ошибочное решение этой задачи, поэтому начнем с его рассмотрения.
int find = 50;
for (int i=0; i<size; i++) {
if (find == numbers[i]) {
printf("Такой элемент есть в массиве\n");
} else {
printf("Такого элемента нет в массиве\n");
}
}
В данной реализации несколько ошибок. Подумайте, какие? Рассмотрим одну из них. Предположим, что элемента в массиве нет, тогда на каждой итерации цикла будет выполняться ветка else, и на экране появятся size сообщений о том, что элемента нет. Если же искомый элемент находится где-то в середине, что программа вначале выведет несколько сообщений об отсутствии, затем – одно сообщение о том, что элемент найден, а затем опять начнет сообщать, что элемента нет.
Что же делать? Нужно заметить два аспекта:
- если элемент найден, то поиск можно заканчивать;
- убедиться в отсутствии элемента можно лишь, пройдя весь массив.
Следующая программа учитывает эти аспекты:
//Искомый элемент
int isFound = 50;
//Нашли или нет
bool found = false;
for (int i=0; i<size; i++) {
if (find == numbers[i]) {
//Отмечаем, что элемент найден
isFound = true;
//Заканчиваем чикл
break;
}
}
//isFound эквивалентно isFound==true
if (isFound) {
printf("Такой элемент есть в массиве\n");
} else {
printf("Такого элемента нет в массиве\n");
}
