Question

напишите программу, которая считает среднее число шагов при двоичном поиске для массива из 32 элементов в диапазоне 0...100. Для поиска используйте 1000 случайных чисел в том же диапазоне. ЯЗЫК PYTHON, ОБЯЗАТЕЛЬНО КОММЕНТАРИЙ НА КАЖДУЮ СТРОЧКУ КОДА,

Answer 1

# подключаем модуль, чтобы использовать случайные числа

from random import *

a = [0]*32   # Создание списка

for i in range (0, 32):

   a[i] = randint(1, 101)  # заполнение случайными числами

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

print(a) # вывод на экран

b = int(input('Введите число для поиска : '))   # ввод числа для поиска

mid = len(a) // 2  # определяем средний элемент списка

low = 0            # определяем верхнюю границу списка

high = len(a) - 1  # определяем верхнюю границу списка

step = 0           # обнуляем счётчик шагов

while a[mid] != b and low <= high:  # в цикле пока не нашли искомый элемент

   if b > a[mid]:  # если искомый элемент > среднего элемента в диапазоне

       low = mid + 1  # то нижнюю границу выставим в середину диапазона

   else:           # если искомый элемент <= среднего элемента в диапазоне

       high = mid - 1 # то верхнюю границу выставим в середину диапазона

   mid = (low + high) // 2  # считаем новый средний элемент диапазона

   step += 1  # увеличиваем счётчик на 1

if low > high:

   print('Нет числа')

else:

   print('Количество шагов = ', step)

   print('Индекс = ', mid)