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

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


=Бинарный поиск=
=Бинарный поиск=
Бинарный поиск - алгоритм, которому необходимо передать отсортированный список. При бинарном поиске каждый раз выбирается число из середины диапазона и исключается половина оставшихся чисел.
Для списка из ''n'' элементов бинарный поиск выполняется за ''log<sub>2</sub>n'' шагов.
'''Пример:'''
* Для списка из ''100 элементов'', потребуется максимум ''7 шагов'', для поиска нужного элемента.
* Для списка из ''100 000 элементов'', потребуется максимум ''17 шагов'', для поиска нужного элемента.
* Для списка из ''1 000 000 элементов'', потребуется максимум ''20 шагов'', для поиска нужного элемента.


=Код=
=Код=

Версия от 21:06, 9 февраля 2020

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


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

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

Для списка из 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

См.также

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