Двоичный поиск. Найти число в упорядоченном массиве

Заполните массив случайными числами, отсортируйте его с помощью метода sort, выведите на экран. Спросите у пользователя число, которое он ищет в этом массиве. Используя метод двоичного поиска найдите этот элемент и выведите на экран его индекс.

from random import random

N = 20
array = []

# заполнение массива
for i in range(N):
    array.append(int(random()*100))

# сортировка массива
array.sort()

print(array)

# число, которое требуется найти
number = int(input())

# нижний (начальный) индекс
low = 0
# верхний (конечный) индекс
high = N-1

# Как только нижний индекс станет
# больше на 1 верхнего или верхний
# на 1 меньше нижнего
# цикл остановится.
while low <= high:

    # Находится индекс середины
    # массива или отрезка массива.
    mid = (low + high) // 2

    # Если искомое число меньше
    # числа с индексом середины,
    if number < array[mid]:
        # то верхняя граница сдвигается
        # к середине (но на 1 до нее,
        # т. к. середина была уже проверена)
        high = mid - 1

    # Если искомое число больше
    # числа с индексом середины,
    elif number > array[mid]:
        # то нижняя граница сдвигается
        # за середину
        low = mid + 1

    # Все остальные случаи возникают,
    # когда искомое число равно числу
    # с индексом mid,
    # т.е. оно есть в массиве и найдено.
    else:
        print("ID =", mid)
        # прерывание цикла
        break

# Ветка else сработает,
# если не было break и
# условие при while стало ложным,
# т.е. тогда, когда нижняя граница
# станет больше верхней. Это значит,
# что в массиве нет искомого числа.
else:
    print("No the number")
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: