Учебник по информатике и математике
Темы
C++
Основы языка
Поиск максимума и минимума в массиве
Оглавление:
Для проекта по географии ты неделю записывал температуру за окном каждое утро: -3, 2, -7, 5, 0, -1, 4. Учитель спрашивает: какой день был самым теплым, а какой — самым холодным?
Ты пробегаешь глазами по списку и держишь в голове лучший результат: «-3… 2 теплее… -7 нет… 5 еще теплее…». Дошел до конца — ответ готов. Компьютер ищет максимум точно так же, только в массиве может быть не семь чисел, а миллион.
Идея алгоритма
Заведем переменную «текущий рекорд» и положим в нее первый элемент массива. Дальше пройдем по остальным элементам по очереди: если элемент больше рекорда, он становится новым рекордом. Когда массив закончится, в переменной будет максимум.
Минимум ищут так же, только новый рекорд ставит элемент, который меньше текущего. Оба рекорда можно обновлять в одном цикле.
Ключевая идея: Начальное значение рекорда — первый элемент массива, а не 0 и не «какое-нибудь маленькое число». Тогда ответ всегда будет одним из элементов массива.
Разбор по шагам
Найдем максимум и минимум температур [-3, 2, -7, 5, 0, -1, 4]. Сначала оба рекорда равны первому элементу, -3. Дальше сравниваем каждый следующий элемент с рекордами:
| Шаг | Элемент | Максимум | Минимум |
|---|---|---|---|
| старт | -3 | -3 | -3 |
| 1 | 2 | 2, потому что 2 > -3 | -3 |
| 2 | -7 | 2 | -7, потому что -7 < -3 |
| 3 | 5 | 5, потому что 5 > 2 | -7 |
| 4 | 0 | 5 | -7 |
| 5 | -1 | 5 | -7 |
| 6 | 4 | 5 | -7 |
Ответ: самая высокая температура 5 градусов, самая низкая -7.
Где находится максимум
Часто нужно знать не только значение, но и место: в какой день было теплее всего. Для этого вместе с рекордом запоминают его индекс и обновляют оба сразу. В нашем массиве максимум стоит на индексе 3. Индексы считаются с нуля, так что это четвертый день записей.
Если максимум встречается несколько раз, важен знак сравнения. Со строгим > запомнится первое вхождение, с >= — последнее. В массиве [3, 8, 1, 8] это индексы 1 и 3.
Реализация
На Python ищем оба рекорда и индекс максимума в одном цикле, а потом проверяем себя встроенными функциями:
temps = [-3, 2, -7, 5, 0, -1, 4]
hi = lo = temps[0] # первый элемент - пока и максимум, и минимум
hi_day = 0 # индекс максимума
for i in range(1, len(temps)):
if temps[i] > hi:
hi = temps[i]
hi_day = i
if temps[i] < lo:
lo = temps[i]
print(hi, hi_day, lo) # 5 3 -7
# То же встроенными функциями
print(max(temps), min(temps)) # 5 -7
print(temps.index(max(temps))) # 3
На C++ то же самое, а вместо встроенных функций — max_element и min_element из библиотеки <algorithm>. Они возвращают итератор (указатель на элемент), поэтому значение достают звездочкой, а индекс получают вычитанием temps.begin():
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> temps = {-3, 2, -7, 5, 0, -1, 4};
int hi = temps[0], lo = temps[0];
int hiDay = 0;
for (int i = 1; i < (int)temps.size(); i++) {
if (temps[i] > hi) {
hi = temps[i];
hiDay = i;
}
if (temps[i] < lo) lo = temps[i];
}
cout << hi << " " << hiDay << " " << lo << "\n"; // 5 3 -7
auto it = max_element(temps.begin(), temps.end());
cout << *it << " " << it - temps.begin() << "\n"; // 5 3
cout << *min_element(temps.begin(), temps.end()) << "\n"; // -7
}
Сложность
Каждый элемент, кроме первого, сравнивается с рекордом один раз. Для массива из $n$ элементов это $n - 1$ сравнение, то есть сложность $O(n)$. Если искать и максимум, и минимум, сравнений будет $2(n - 1)$ — это по-прежнему $O(n)$.
Быстрее не получится: алгоритм, который пропустит хотя бы один элемент, может пропустить именно максимум. Встроенные max() и min() тоже проходят весь список. Поэтому запись temps.index(max(temps)) проходит по списку дважды: первый раз ищет максимум, второй — его индекс. Ручной цикл справляется за один проход.
Частые ошибки
- Начать с
hi = 0. Для массива[-5, -2, -8]получится 0, хотя такого числа в массиве нет. Начинай с первого элемента. - Сравнивать с
>=, когда нужен первый максимум. Индекс окажется последним из равных. - Забыть про пустой массив. У него нет
temps[0], и программа упадет. Если массив может быть пустым, проверь это до поиска.
Частая ошибка: Не называй переменную
maxилиminв Python. Встроенная функция с этим именем перестанет работать, и вызовmax(temps)дальше в программе закончится ошибкой.
Проверь себя
Миша искал максимум так: hi = 0, а потом для каждого x из списка [-5, -2, -8] выполнял if x > hi: hi = x. Чему будет равно hi в конце?
Сколько сравнений с текущим максимумом сделает алгоритм в массиве из 10 элементов?
Соедини функцию и то, что она возвращает.
max(a)
Наименьший элемент списка в Python
min(a)
Индекс первого вхождения x в список
a.index(x)
Наибольший элемент списка в Python
max_element(a.begin(), a.end())
Итератор на наибольший элемент в C++