Открывается в новой вкладке

Мы всегда на связи

Пишите в любое удобное время:
whatsappvktelegramMAX
Или задайте вопрос через форму:

Мы всегда на связи

Заявка принята!

Мы уже получили заявку и скоро свяжемся. Расскажите немного о ребёнке — так быстрее подберём группу (необязательно).

Спасибо!

Мы свяжемся с вами в ближайшее время.

Учебник по информатике и математике

Структурированные пути обучения: от первых программ до олимпиад и вступительных в топ-школы.
    Темы
    Заниматься с наставником
    прочитали
    3 задачи

    Поиск максимума и минимума в массиве

    Оглавление:

    Для проекта по географии ты неделю записывал температуру за окном каждое утро: -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) дальше в программе закончится ошибкой.

    Проверь себя

    1.

    Миша искал максимум так: hi = 0, а потом для каждого x из списка [-5, -2, -8] выполнял if x > hi: hi = x. Чему будет равно hi в конце?

    2.

    Сколько сравнений с текущим максимумом сделает алгоритм в массиве из 10 элементов?

    3.

    Соедини функцию и то, что она возвращает.

    max(a)

    Наименьший элемент списка в Python

    min(a)

    Индекс первого вхождения x в список

    a.index(x)

    Наибольший элемент списка в Python

    max_element(a.begin(), a.end())

    Итератор на наибольший элемент в C++

    Поможем подобрать обучение

    Оставьте телефон. Мы перезвоним, поможем выбрать подходящие занятия и ответим на вопросы

    Поможем подобрать обучение

    Заявка принята.

    Мы свяжемся с вами