Python:Примеры/Бинарный поиск: различия между версиями

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

(Новая страница: «{{Python/Панель перехода}} {{Myagkij-редактор}} =Бинарный поиск= =Код= <syntaxhighlight lang="python" line="GESHI_NORMAL…»)
 
Строка 4: Строка 4:
  
 
=Бинарный поиск=
 
=Бинарный поиск=
 +
 +
Бинарный поиск - алгоритм, которому необходимо передать отсортированный список. При бинарном поиске каждый раз выбирается число из середины диапазона и исключается половина оставшихся чисел.
 +
 +
Для списка из ''n'' элементов бинарный поиск выполняется за ''log<sub>2</sub>n'' шагов.
  
 
=Код=
 
=Код=

Версия 20:03, 9 февраля 2020

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


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

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

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

Код

 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

См.также

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