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

См.также

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