Поиск элемента в массиве
💻 Информатика · 8 класс
Линейный поиск, поиск максимума и минимума, подсчёт элементов по условию в одномерном массиве.
Зачем искать элементы в массиве
Массив — это упорядоченный набор однотипных элементов, у каждого из которых есть свой номер, называемый индексом. По индексу можно обратиться к любому элементу напрямую. Очень часто в программе требуется найти в массиве элемент с нужным свойством: например, заданное значение, наибольший или наименьший элемент, либо подсчитать, сколько элементов удовлетворяют некоторому условию. Для всех этих задач применяют алгоритмы, основанные на переборе элементов в цикле.
Линейный поиск значения
Самый простой способ найти значение — линейный поиск. Элементы массива перебирают по очереди, от первого до последнего, и каждый сравнивают с искомым значением. Как только встретится совпадение, можно запомнить номер этого элемента в специальной переменной и при необходимости отметить, что значение найдено.
нашли := нетнц для i от 1 до nесли A[i] = искомое то нашли := да; номер := iкц
Если после перебора переменная нашли осталась равной «нет», значит, искомого значения в массиве нет вовсе. Линейный поиск всегда даёт верный ответ, потому что проверяет каждый элемент без исключения. Его применяют, когда элементы расположены в произвольном порядке.
Поиск наибольшего элемента
Чтобы найти максимум, за начальное значение принимают первый элемент массива. Затем проходят по остальным элементам и, встретив значение больше текущего максимума, обновляют его. После прохода переменная содержит наибольший элемент.
макс := A[1]нц для i от 2 до nесли A[i] > макс то макс := A[i]кц
Поиск наименьшего элемента устроен точно так же, только знак сравнения меняется на противоположный, а переменную называют минимумом. Важно, что за начальное значение и максимума, и минимума берут именно первый элемент массива, а затем сравнивают его с остальными по очереди.
Подсчёт элементов по условию
Чтобы сосчитать элементы с нужным свойством, заводят счётчик, изначально равный нулю, и увеличивают его на единицу всякий раз, когда очередной элемент удовлетворяет условию. Например, так можно сосчитать все положительные числа в массиве.
| Задача | Что готовим заранее | Что делаем в цикле |
|---|---|---|
| Поиск значения | флаг «не найдено» | сравниваем с искомым |
| Максимум | максимум равен первому | обновляем, если больше |
| Минимум | минимум равен первому | обновляем, если меньше |
| Подсчёт | счётчик равен нулю | увеличиваем по условию |
Частая ошибка: искать максимум, начав со значения ноль. Если все элементы массива отрицательные, такой алгоритм даст неверный ответ. Поэтому начальное значение максимума берут равным первому элементу массива, а не нулю.
Кратко о главном
- Массив — набор однотипных элементов с индексами.
- Линейный поиск перебирает элементы по очереди.
- Максимум и минимум начинают искать с первого элемента.
- Для подсчёта по условию используют счётчик.
- Все эти алгоритмы строятся на цикле перебора.