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

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

(Новая страница: «{{Python/Панель перехода}} {{Myagkij-редактор}} =Бинарный поиск= =Код= <syntaxhighlight lang="python" line="GESHI_NORMAL…»)
(нет различий)

Версия 19:57, 9 февраля 2020

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


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

Код

  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

См.также

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