Двоичный поиск — это алгоритм поиска элемента в отсортированном массиве, который работает за логарифмическое время. Основная идея заключается в том, чтобы на каждом шаге делить массив пополам и сравнивать средний элемент с искомым значением. Если средний элемент равен искомому, поиск завершается. Если искомое значение меньше среднего элемента, поиск продолжается в левой половине массива. Если искомое значение больше среднего элемента, поиск продолжается в правой половине массива. “Разделяй и сокращай вдвое”
Каждый раз смотри в середину, и если не угадал — выброси половину. “Середина. Больше — направо. Меньше — налево. Нашёл — готово.”
Двоичный поиск — это алгоритм поиска элемента в отсортированном массиве, который работает за логарифмическое время. Основная идея заключается в том, чтобы на каждом шаге делить массив пополам и сравнивать средний элемент с искомым значением. Если средний элемент равен искомому, поиск завершается. Если искомое значение меньше среднего элемента, поиск продолжается в левой половине массива. Если искомое значение больше среднего элемента, поиск продолжается в правой половине массива.
Алгоритм двоичного поиска можно описать следующими шагами:
📥 Что на входе?
- Массив: [1, 3, 5, 7, 9, 11, 13] — отсортирован
- Ищем число, например: 7
🧠 Основная идея:
“Разделяй и сокращай вдвое”
Каждый раз смотри в середину, и если не угадал — выброси половину.
🔢 Пошагово:
- left = 0 → начало массива
- right = len(массива) - 1 → конец
- Пока left <= right:a. mid = (left + right) // 2 ← середина (целое число)
b. Посмотри на a[mid]:✅ Равно искомому? → Ура! Верни mid.
🔽 Искомое меньше? → Ищи слева: right = mid - 1
🔼 Искомое больше? → Ищи справа: left = mid + 1 - Если вышли из цикла и не нашли → верни -1
✍️ Как запомнить:
“Середина. Больше — направо. Меньше — налево. Нашёл — готово.”