Бинарный поиск — это эффективный алгоритм для поиска целевого значения в отсортированном массиве. Он работает путём многократного деления пространства поиска пополам, достигая временной сложности O(log n) — намного лучше, чем линейный поиск с O(n).
Алгоритм использует два указателя, left и right, чтобы определить текущие границы поиска:
left = 0 и right = len(arr) - 1mid = (left + right) // 2arr[mid] с целевым значением:
arr[mid] меньше целевого значения — ищи правую половину, установив left = mid + 1arr[mid] больше целевого значения — ищи левую половину, установив right = mid - 1-1, чтобы обозначить, что целевое значение не найденоdef binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid # Target found: return index
elif arr[mid] < target:
left = mid + 1 # Search right half
else:
right = mid - 1 # Search left half
return -1 # Target not found
-1, если не найдено// (целочисленное деление), чтобы гарантировать, что mid всегда является корректным индексом массиваБинарный поиск требует, чтобы входной массив был отсортирован, и он даст неправильные результаты, если применить его к неотсортированному массиву.
Новый — ещё не проверен сообществом
Вы