Линейный поиск. Минимальный и максимальный элементы массива

Выполнить линейный поиск первого вхождения целого значения, явно обозначить отсутствие; найти минимум и максимум непустого массива с правильным началом. Различать индекс и элемент, сохранить и выполнить свои программы на повторах, отрицательных значениях, крайних позициях и отсутствии искомого.

Все значения условные целые. Поиск возвращает именно первый неотрицательный индекс совпадения; если его нет, по принятому в программе контракту pos = -1. В Python a[-1] допустимо и означает последний элемент непустого списка, поэтому перед обращением по результату поиска проверяют pos >= 0. Отсутствие не превращают в последний найденный элемент. Минимум и максимум здесь — значения элементов, не их индексы. В непустом списке начальные low и high берут из a[0]; у пустого массива этих экстремумов нет, программа выводит empty. Встроенные min/max/index не заменяют изучаемый обход. Подготовленный Python 3, без пакетов, внешних аккаунтов и персональных данных.

Для основной цифровой практики нужна заранее подготовленная школьная среда из инструкции учителя. Прогноз и итог записывай на бумаге; при отсутствии техники цифровое действие проверяют на ближайшей компьютерной практике. Сохраняй первую попытку; исправления отмечай другим знаком.

Безопасное начало

Сухие руки, без напитков у техники. Провода и разъёмы не трогай, о неисправности сообщи учителю. Работай по правилам кабинета. Две полные минуты в середине урока — без экрана и заданий. Внешний ИИ, личные аккаунты и личные данные не требуются.

Что уже нужно знать

Из 8 класса: if, while, сравнения, логическое and, присваивание и отступы. Из 016–017: список Python, индексы с нуля, len, обход и собственные сохранённые .py. Новое — первое вхождение, специальное обозначение отсутствия, минимум/максимум от первого элемента. Двоичного поиска, сортировки и доказательства асимптотики в этом часе нет.

S0. В списке [5, 0, 5] искомое значение 5. Чем отличаются само значение и номер позиции с нуля? Может ли одно значение находиться в двух позициях?

Устная проба без отметки.

Искомое значение, найденный индекс и экстремумы

Линейный поиск последовательно проверяет элементы. Здесь договорились возвращать первый индекс совпадения, начиная с нуля. До поиска pos = -1; обновлять pos на i только при pos == -1 и a[i] == target. После первого совпадения защита сохраняет найденную позицию. Если проверять только равенство элементов и обновлять при каждом совпадении, останется последнее вхождение. При отсутствии pos = -1 — специальный результат по контракту. Python a[-1] обращается к последнему элементу, поэтому перед использованием найденного индекса нужно проверить pos >= 0; иначе сообщить «не найдено». Для минимума и максимума непустого списка начать low = a[0] и high = a[0], затем сравнивать остальные значения и обновлять кандидатов. Ноль не является универсальным началом: ошибочен для минимума положительных и максимума отрицательных. У пустого списка a[0] нет; экстремумы без дополнительного определения не вычисляют, здесь выводят empty. Во всех циклах переход i выполняют независимо от успеха сравнения. До запуска — прогноз, после — реальный вывод своего сохранённого .py.

Отрицательное значение элемента и отрицательный индекс — разные понятия. В этом уроке результаты найденных позиций неотрицательные. Перед обращением по pos проверяют результат поиска.

Концептуальная иллюстрация. Точные данные определены условиями, таблицами и схемами; предметы на рисунке не являются входными данными.

Личная проба

C1. Python 3: a = [2, 9, 9], ищут первое вхождение значения 9. Запиши найденный индекс и значение в найденной позиции. Индексы начинаются с нуля.

Одна минута лично, одна на сравнение индекса и значения. Памятка разрешена.

Проследить первое совпадение

Другой пример: [6, 1, 6], target = 6. Сначала pos = -1. При i = 0 совпадение и ещё нет найденного: pos = 0. При i = 1 и i = 2 составное условие уже ложно из-за pos != -1. Итог 0, найденное значение 6. Повтор в конце не перезаписывает первый индекс.

A1. a = [8, 3, 8, 1], target = 8. До обхода pos = -1. Для каждого i = 0, 1, 2, 3: только если pos == -1 и a[i] == target, выполнить pos = i. После каждого элемента запиши pos. Какое вхождение найдено? Что будет, если убрать проверку pos == -1?

Заготовка для своей записи:

Сначала своя запись и основание, затем сверка.

Полная пауза

Две минуты без проекции, чтения, вычислений и обсуждения. Отведи взгляд и смени позу.

Кандидат должен происходить из входа

Другой пример: [-3, -8], high = a[0] = -3. Второе -8 не больше кандидата; максимум -3. Начало high = 0 ошибочно оставило бы не входное число. Для минимума [5, 8] аналогично начать low = 5; произвольный 0 не подойдёт. В A2 другой отрицательный список.

A2. Выпиши вывод ошибочной программы Python 3 ниже. Является ли он максимальным элементом данного списка? Исправь только начальное high, не меняя список и цикл. Почему к a[0] нельзя обращаться у пустого []?

a = [-4, -7, -2]
high = 0
i = 0
while i < len(a):
    if a[i] > high:
        high = a[i]
    i = i+1
print(high)

Две минуты лично и две на проверку начального кандидата; в коротком варианте две лично и одна сверка.

Концептуальная иллюстрация. Точные данные определены условиями, таблицами и схемами; предметы на рисунке не являются входными данными.

Три случая собственной программы

Каркас содержит два последовательных блока: поиск первого индекса, затем экстремумы. Дополняются только три TODO. Сохранить свой исходный файл, отдельную копию с явно другими входными данными и третью копию с изменённым только target. Перед каждым запуском прогноз двух строк; после — фактический вывод. Третий случай должен показать отсутствие при прежних экстремумах.

B1. Лично в заранее готовом Python 3 открой search-starter.py. В нём три строки TODO: pos = -1 внутри найденного совпадения, low = 0 и high = 0 перед обходом экстремумов. Дополни их: сохранять индекс i первого совпадения, а оба начальных экстремума брать из первого входного элемента a[0]. Условие pos == -1, проверки пустоты и остальные отступы сохрани.

1. Даны a = [4, -2, 4, 7, -2], target = 4. До запуска запиши прогноз двух строк: найденный первый индекс; затем минимум и максимум. Сохрани свой search_A.py/search_B.py, проверь путь, запусти именно сохранённый файл и выпиши реальный вывод.

2. Сохрани отдельную копию negative_A.py/negative_B.py. В ней явно измени входные данные на a = [-5, -5, -2, -9], target = -9. До запуска запиши новый прогноз, сохрани и запусти. Здесь проверяются полностью отрицательный список, повторы и совпадение в последней позиции.

3. Сделай третью копию absent_A.py/absent_B.py из второй. Измени только target на 8, список сохрани. Спрогнозируй отсутствие, сохрани, запусти и сравни две строки вывода. Не обращайся к a[pos] при pos = -1. У каждого три своих файла, три реальных запуска и журнал с именами/путями, прогнозами и фактическими выводами.

Заготовка для своей записи:

Четырнадцать минут: 1 инструкция + 6 первый ученик + 6 второй + 1 личная сверка. При 30 ПК параллельно. У каждого три своих сохранённых файла и три реальных запуска; среда и папки подготовлены до урока.

Проверка вымышленного ответа ИИ

AI1. Вымышленный ИИ утверждает: «Максимум всегда можно начинать с 0. А pos = -1 после поиска — это найденный последний элемент, можно сразу вывести a[pos]». Опровергни обе фразы. Для первой дан список [-5, -8]. Во второй -1 заранее объявлен результатом «не найдено».

Это заранее составленный учебный пример. Самостоятельно проверь конкретный шаг; обращение к сервису не требуется.

Помощь и резерв

• Выдаёт значение за индекс. Подпиши позиции с нуля отдельно от значений.
• Перезаписывает первое совпадение. Проверь защиту pos == -1 перед обновлением.
• Начинает экстремум с нуля. Возьми первый входной элемент после проверки непустоты.
• Считает -1 успешным поиском. Сначала проверь pos >= 0; иначе сообщение об отсутствии.
• Смотрит старый вывод. Проверь имя, путь и сохранение конкретной копии.

D1. Резерв на бумаге. Список [5, 8] непуст. Какой минимум получится, если начать low = 0 и заменять его только меньшими входными значениями? Как нужно начать и каков правильный минимум?

D1 — необязательный резерв на 3–4 минуты после основных попыток. При нехватке времени перенести. H1 и весь тест автоматически вместе не назначаются.

Индивидуальный итог

Четыре полные минуты лично. Условия заранее на бумаге. Памятка и разобранные модели разрешены; ключи и веб-разбор закрыты. Учитель не даёт учебных подсказок. Сбор после четырёх минут.

E1. В списке [3, 8, 3, 1] найди первый индекс значения 3, минимальное и максимальное значения. Индексы с нуля.

E2. Непустой список состоит из [-6, -4]. С какого значения начать поиск максимума и почему начальное 0 не подходит?

E3. По принятому контракту поиск вернул pos = -1. Можно ли выводить a[pos] как найденное значение? Что сделать вместо этого?

Разбор после своей попытки

Показать ответ после выполнения

После исправления выбери один новый пример из самопроверки.

Файлы для собственной практики

• Python — поиск и экстремумы

Распакуй ZIP до урока и открой search-starter.py в готовом школьном Python 3. Три строки TODO намеренно неполны. Готового решённого B1 и личных наблюдений в архиве нет. Контракт -1 и проверка пустоты уже заданы; перед каждым запуском сверяй сохранённое имя и входные данные.

Материалы и самопроверка

Презентация, самостоятельный план учителя, рабочий лист, выходной билет и бумажная самопроверка открываются отдельными карточками. DOCX можно смотреть на сайте и скачать. PDF для печати:

• Рабочий лист
• Выходной билет — два на А4
• Самопроверка на бумаге

Самопроверка на сайте: шесть вопросов с пояснениями, отдельно 6–8 минут. Бумажная версия с письменными основаниями и разбором — 8–12 минут. Все шесть новых письменных случаев — ещё 8–10 минут; выбирай прежде всего случай к своей ошибке. Эти модули не прибавляют к основным 45 минутам и не задаются целиком вместе с H1 автоматически. Пояснения и новые случаи для бумажного разбора есть в плане учителя.

Домашний перенос

H1. Дома 5–7 минут на бумаге. a = [-3, 6, -3, 0]. Для target = -3 найди первый индекс, минимум и максимум. Затем меняется только target на 0, а потом на 5: укажи результат поиска в каждом случае. -1 обозначает отсутствие. ПК не нужен.

Полное условие и памятка есть на листе. Решение запиши в тетради. Достаточно 5–7 минут с сохранённой опорой.

Источники

ФРП информатики 7–9 классов, базовый уровень, содержание 9 класса на печатных с. 10–12, результаты с. 19–20 и тематическое планирование с. 41–42. Соответствующий час авторского КТП 2026/2027. Содержание не расширяется до углублённого курса и не подменяется подготовкой к экзамену. Учебник школы не указан; номера параграфов не назначены.

• Федеральная рабочая программа информатики 7–9 классов, базовый уровень
• Информационно-методическое письмо по информатике на 2026/2027 год
• Python — списки, индексы и отрицательный индекс
• Python — ветвление и управление обходом