Линейный и бинарный поиск

Линейный поиск

Самый простой способ найти элемент в спискеИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list. — пройти его по порядку и сравнивать каждый элемент с искомым. Это линейный поиск. Он работает на любом списке, даже неотсортированном, но в худшем случае придётся просмотреть все элементы.

Принято возвращать индексНомер позиции элемента в последовательности. В Python нумерация с нуля: первый элемент — индекс 0. найденного элемента, а если элемента нет — особое значение -1 (такого индекса не бывает у обычного списка). ФункцияИменованный блок кода, который можно вызывать многократно. Может принимать аргументы и возвращать результат. enumerate даёт сразу индекс и значение.

Бинарный поиск — поиск в отсортированном списке

Если список уже отсортирован, можно искать гораздо быстрее. Вспомните, как ищут слово в словареКоллекция пар «ключ → значение»: {"a": 1}. Быстрый доступ по ключу. По-английски dict.: открывают примерно посередине, смотрят, в какой половине нужное слово, и отбрасывают вторую половину. Бинарный поиск делает то же самое: каждый шаг вдвое сокращает зону поиска.

Вернётся 3. Шаги: mid=2 (значение 6, меньше 8 → идём вправо, low=3), затем mid=3 (значение 8 — нашли). Всего два сравнения вместо четырёх у линейного поиска.

⚠️ Частые ошибки новичков

Ошибка. Забыть обновить границы и написать low = mid вместо low = mid + 1. Тогда при неудачном сравнении зона поиска перестаёт сужаться и циклКонструкция, повторяющая блок кода: for перебирает элементы, while — пока условие истинно. зацикливается навсегда. Запустите сломанный код — он зависнет (прервите его). Почините: сдвигайте границу за mid.