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 и камерой или например его можно использовать при откладке своей программы..

Answer 2

Конечно, вот пример бинарного поиска на Python. Предположим, у вас есть отсортированный список чисел, и вы хотите найти определенное число в этом списке. Бинарный поиск поможет вам это сделать эффективно:

pythonCopy code
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Находим средний индекс

        if arr[mid] == target:
            return mid  # Нашли элемент, возвращаем его индекс
        elif arr[mid] < target:
            left = mid + 1  # Искать в правой половине
        else:
            right = mid - 1  # Искать в левой половине

    return -1  # Элемент не найден

# Пример использования
my_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target_element = 11
result = binary_search(my_list, target_element)

if result != -1:
    print(f"Элемент {target_element} найден в списке, его индекс: {result}")
else:
    print(f"Элемент {target_element} не найден в списке.")

Этот код ищет значение target_element в отсортированном списке my_list. Если элемент найден, он вернет его индекс; в противном случае, вернет -1. Этот алгоритм работает быстро для больших отсортированных списков, так как на каждой итерации он сокращает область поиска вдвое.