Question

Информатика.
Бинарный поиск. Привести пример.
Помогите!​

Answer 1

Пример?

Ну если под "примером" понимается сам код бинарного поиска, то на питоне он будет выглядеть так:

def binary_search(list, item):

___low = 0  

___high = len(list) - 1  

___while low <= high:

______mid = int((low + high) / 2)

______guess = list[mid]

______if guess == item:

_________return mid

______if guess > item:

_________high = mid - 1  

______else:

_________low = mid + 1

___return None

my_list = [1, 3, 5, 7, 9, 11, 12, 13, 14, 15, 20]

print(binary_search(my_list, 3)) # => 1 т.к. число 3 стоит под индексом [1]

print(binary_search(my_list, -1)) # => None(ничего), элемент не найден

Работает быстрее обычного поиска в перспективе т.к. скорость выполнения обычного поиска n шагов, а у бинарного log2n. Работает только тогда, когда список отсортирован (от 1 до n по порядку).

Сопоставим с игрой "угадай число" где ты загадываешь любое число от 1 до 100 и говоря мне больше или меньше, я его угадываю.

Например загадано число 76.

Я отсекаю половину списка (говорю 50) - больше

Я знаю, что твое число находится в диапазоне от 50 до 100. Опять половину - 75 (больше)

Мы отекли уже 74 числа всего за 2 шага. И подобным образом находим в итоге то число, которое нам нужно.

А используется много где.. Даже в тех же самых 3D играх, где пространство делится на древовидную структуру, и двоичный поиск используется для получения того, какие подразделения отображать в соответствии с позицией 3D и камерой или например его можно использовать при откладке своей программы..