Урок 12.2
Если список отсортирован, искать можно вдвое быстрее: смотреть в середину и выкидывать половину.
def binary_search(numbers, target):
left, right = 0, len(numbers) - 1
while left <= right:
mid = (left + right) // 2
if numbers[mid] == target:
return mid
elif numbers[mid] < target:
left = ... # правая половина
else:
right = ... # левая половина
return -1
left и right — границы куска, где ещё может быть ответ;// — целое деление: индекс не бывает дробным;left = mid + 1 и right = mid - 1 отбрасывают половину; без +1 и -1
цикл зациклится;Проверка даёт отсортированный список numbers и число target.
Напишите binary_search и напечатайте индекс найденного или -1.
Держите две границы куска, где ещё может быть ответ, и сужайте его вдвое.
Середина — (left + right) // 2: целое деление, индекс не бывает дробным.
Сдвигать границы нужно на mid + 1 и mid - 1, иначе цикл зациклится.
Цикл идёт, пока left <= right.