Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Two approaches to binary search
- Разберём решение и посмотрим, как та же задача решается другим способом.
- Задача
- Дан отсортированный список чисел arr и число target. Найти его индекс или вернуть -1, если элемента нет.
- Решение
- ``python
- def binary_search(arr: list[int], target: int) -> int:
- lo, hi = 0, len(arr) - 1
- while lo <= hi:
- mid = (lo + hi) // 2
- if arr[mid] == target:
- return mid
- if arr[mid] < target:
- lo = mid + 1
- else:
- hi = mid - 1
- return -1
- print(binary_search([1, 3, 5, 7, 9, 11], 7))
- `
- Как это работает
- На каждом шаге диапазон поиска сокращается вдвое: если середина меньше цели — ищем справа, иначе слева. Отсюда и логарифмическая скорость.
- Пример работы
- `text
- 3
- ``
- Сложность
- O(log n) по времени, O(1) по памяти.
- Альтернативный подход
- Ту же задачу часто решают иначе: например, через рекурсию вместо цикла или через стандартную библиотеку вместо ручной реализации. Альтернатива обычно короче, но первое «ручное» решение лучше показывает механику работы алгоритма. Полезно написать оба и сравнить на одинаковых тестах.
- Оба подхода рабочие; важно понимать цену каждого, а не копировать первый попавшийся.
- View Full Gallery → https://go.cbrop.com/prse
- Related:
- https://discuss.tchncs.de/post/65440183
- https://posts.workshop-hub.workers.dev/quicksort-dva-sposoba
- https://ymcatexasyg.org/wp-content/uploads/event-manager-uploads/event_banner/2026/11/alice-in-cradle-cg-31d06a.pdf
- https://news-ctl-posts.hashnode.dev/pitfalls-of-bracket-sequence-validation-mwefavwq
- https://pastebin.com/LwMLrZ0n
Advertisement
Add Comment
Please, Sign In to add comment