Бинарный поиск
Приведенный в статье код написан на python
Важнейший поисковый алгоритм, позволяющий искать значение в отсортированном списке с выдающейся скоростью, сложность которого составляет O(log2 n). На практике это значит, что для нахождения элемента в списке длиной n понадобится:
• n = 2(1 попытка)
• n = 4(2 попытки)
• n = 8(3 попытки)
• n = 16(4 попытки)
• n = 32(5 попыток)
• n = 64(6 попыток)
• n = 128(7 попыток)
• n = 256(8 попыток)
и так далее...
Длина списка растет квадратично пока сложность поиска растет линейно. Для сравнения, если мы попробуем найти случайный элемент в списке из 16 777 216 значений, и сделаем это проверяя каждый элемент по порядку, в худшем случае нам потребуется 16 777 216 проверок, а в среднем 8 388 608, тогда как Бинарный поиск, найдет его всего за 24 попытки максимум!
Как это работает?
Предположим у нас есть отсортированный список лет в пределах [1900, ... , 2025].
array = list(range(1900, 2025+1))
Я загадал год.
value = random(1900, 2025+1)
Вы угадываете: 1900?
-Нет
-1901?
-Нет
...
Из этого следует, что при каждой догадке, потенциальный список уменьшается на единицу. Но мы можем лучше!
Многим из нас знакома игра на поиск "горячо, холодно" и она как никогда лучше описывает алгоритм бинарного поиска.
Для начала разделим список на 2 части по середине.
Нам понадобятся:
• min - Начальный индекс, который по умолчанию для массива равен 0
• max - Наибольший индекс, равный длине массива - 1, т.к. индексация начинается с 0
• mid - Среднее для минимального и наибольшего значения
min = 0
max = len(array) - 1
mid = (min + max) // 2 # В этом случае, если сумма будет нечетной, то дробная часть будет усечена.
Теперь проверим, является ли загаданное число равным тому, что хранится под индексом (mid).
if array[mid] == value:
return mid # Нашовся!
Вероятность нахождения с первой попытки разумеется не велика, так что обработаем варианты когда значение под индексом (mid) больше или меньше искомого.
if array[mid] < value:
min = mid + 1 # Искомое значение больше среднего, переставляем минимальный индекс на шаг выше среднего.
else:
max = mid - 1 # Искомое значение меньше среднего, переставляем максимальный индекс на шаг ниже среднего.
Таким образом мы сократили единственной проверкой весь проверяемый список вдвое! Осталось повторить эту операцию несколько раз, пока мы не найдем желанное значение, или укажем юзеру на то, что его в списке нет.
Составим функцию целиком, обернув ее в цикл.
def binary_search(array, target):
min = 0
max = len(array) - 1
max = len(array) - 1
while min <= max:
mid = (min + max) // 2
if array[mid] == target:
if array[mid] == target:
return mid
elif array[mid] < target:
min = mid + 1
min = mid + 1
else:
max = mid - 1
return -1 # Элемент не найден
Равенство min и max в цикле while min <= max: приведет к проверке последнего оставшегося индекса, если его значение не будет равно искомому, то отработает один из вариантов min = mid + 1 или max = mid - 1, после чего цикл вернет return -1.
алгоритмы
поиск
python
