Python:Примеры/Бинарный поиск

Материал из Онлайн справочника
Перейти к: навигация, поиск

Проверка/Оформление/Редактирование: Мякишев Е.А.


Бинарный поиск

Бинарный поиск - алгоритм, которому необходимо передать отсортированный список. При бинарном поиске каждый раз выбирается число из середины диапазона и исключается половина оставшихся чисел.

Для списка из n элементов бинарный поиск выполняется за log2n шагов.

Пример:

  • Для списка из 100 элементов, потребуется максимум 7 шагов, для поиска нужного элемента.
  • Для списка из 100 000 элементов, потребуется максимум 17 шагов, для поиска нужного элемента.
  • Для списка из 1 000 000 элементов, потребуется максимум 20 шагов, для поиска нужного элемента.

Код

  1. def binary_search(list, item):
  2.   # в low и high хранятся границы части списка, где выполняется поиск
  3.   low = 0
  4.   high = len(list) - 1
  5.   i = 0
  6.   # Пока не останется один элемент
  7.   while low <= high:
  8.     # Проверяем средний элемент
  9.     mid = (low + high) // 2
  10.     guess = list[mid]
  11.     # Значение найдено
  12.     if guess == item:
  13.       return mid
  14.     # Значение велико
  15.     if guess > item:
  16.       high = mid - 1
  17.     # Значение мало
  18.     else:
  19.       low = mid + 1
  20.     i=i+1
  21.     print(i)
  22.  
  23.   # Значение не найдено
  24.   return None
  25.  
  26. my_list = [1, 3, 5, 7, 9]
  27. print(binary_search(my_list, 3)) # => 1 (позиция элемента в списке)
  28.  
  29. # 'None' в Python означает "ничто". Элемент не найден.
  30. print(binary_search(my_list, -1)) # => None

См.также

Внешние ссылки