Python:Примеры/Бинарный поиск
Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску
Проверка/Оформление/Редактирование: Мякишев Е.А.
Бинарный поиск
Бинарный поиск - алгоритм, которому необходимо передать отсортированный список. При бинарном поиске каждый раз выбирается число из середины диапазона и исключается половина оставшихся чисел.
Для списка из n элементов бинарный поиск выполняется за log2n шагов.
Пример:
- Для списка из 100 элементов, потребуется максимум 7 шагов, для поиска нужного элемента.
- Для списка из 100 000 элементов, потребуется максимум 17 шагов, для поиска нужного элемента.
- Для списка из 1 000 000 элементов, потребуется максимум 20 шагов, для поиска нужного элемента.
Код
def binary_search(list, item):
# в low и high хранятся границы части списка, где выполняется поиск
low = 0
high = len(list) - 1
i = 0
# Пока не останется один элемент
while low <= high:
# Проверяем средний элемент
mid = (low + high) // 2
guess = list[mid]
# Значение найдено
if guess == item:
return mid
# Значение велико
if guess > item:
high = mid - 1
# Значение мало
else:
low = mid + 1
i=i+1
print(i)
# Значение не найдено
return None
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # => 1 (позиция элемента в списке)
# 'None' в Python означает "ничто". Элемент не найден.
print(binary_search(my_list, -1)) # => None
