pb1a38a600

Two approaches to binary search

Nov 17th, 2026
9
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.19 KB | None | 0 0
  1. Two approaches to binary search
  2.  
  3. Разберём решение и посмотрим, как та же задача решается другим способом.
  4.  
  5. Задача
  6.  
  7. Дан отсортированный список чисел arr и число target. Найти его индекс или вернуть -1, если элемента нет.
  8.  
  9. Решение
  10.  
  11. ``python
  12. def binary_search(arr: list[int], target: int) -> int:
  13. lo, hi = 0, len(arr) - 1
  14. while lo <= hi:
  15. mid = (lo + hi) // 2
  16. if arr[mid] == target:
  17. return mid
  18. if arr[mid] < target:
  19. lo = mid + 1
  20. else:
  21. hi = mid - 1
  22. return -1
  23.  
  24. print(binary_search([1, 3, 5, 7, 9, 11], 7))
  25. `
  26.  
  27. Как это работает
  28.  
  29. На каждом шаге диапазон поиска сокращается вдвое: если середина меньше цели — ищем справа, иначе слева. Отсюда и логарифмическая скорость.
  30.  
  31. Пример работы
  32.  
  33. `text
  34. 3
  35. ``
  36.  
  37. Сложность
  38.  
  39. O(log n) по времени, O(1) по памяти.
  40.  
  41. Альтернативный подход
  42.  
  43. Ту же задачу часто решают иначе: например, через рекурсию вместо цикла или через стандартную библиотеку вместо ручной реализации. Альтернатива обычно короче, но первое «ручное» решение лучше показывает механику работы алгоритма. Полезно написать оба и сравнить на одинаковых тестах.
  44.  
  45. Оба подхода рабочие; важно понимать цену каждого, а не копировать первый попавшийся.
  46.  
  47. View Full Gallery → https://go.cbrop.com/prse
  48.  
  49. Related:
  50.  
  51. https://discuss.tchncs.de/post/65440183
  52. https://posts.workshop-hub.workers.dev/quicksort-dva-sposoba
  53. https://ymcatexasyg.org/wp-content/uploads/event-manager-uploads/event_banner/2026/11/alice-in-cradle-cg-31d06a.pdf
  54. https://news-ctl-posts.hashnode.dev/pitfalls-of-bracket-sequence-validation-mwefavwq
  55. https://pastebin.com/LwMLrZ0n
  56.  
Advertisement
Add Comment
Please, Sign In to add comment