Question

Заполнить массив случайными числами и отсортировать его. Ввести число x.Используя двоичный поиск, определить, есть ли в массиве число, равно x.Подсчитать количество сравнений. Обязательно комментарий в каждой строке кода, ЯЗЫК PYTHON Пример:Массив : 1 4 7 3 9 2 4 5 2После сортировки : 1 2 2 3 4 4 5 7 9Введите число x: 2Число 2 найденоКоличество сравнений: 2

Answer 1

Ответ:

from random import randint

ms = [randint(0, 9) for i in range(15)] #заполнение массива (списка)

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

count = 0

print(ms)

x = int(input())

mid = len(ms) // 2

low = 0

high = len(ms) - 1

while 1:

 mid = len(ms) // 2

 low = 0

 high = len(ms) - 1  

 while ms[mid] != x and low <= high:

   if x > ms[mid]:

     low = mid + 1

   else:

     high = mid - 1

   mid = (low + high) // 2

 if low > high:

     break

 else:

     ms.pop(mid)

     count += 1

print("колво чисел", x, "-", count) # итог

Объяснение:

Answer 2

Для решения данной задачи можно использовать алгоритм двоичного поиска.

Сначала необходимо заполнить массив случайными числами. Для этого можно воспользоваться функцией `random.randint()` из модуля `random`.

Затем массив нужно отсортировать. Для этого можно воспользоваться методом `sort()`.

После этого, пользователю необходимо ввести число `x`, которое нужно найти в массиве.

Далее, приступаем к двоичному поиску. Заведем переменные `left` и `right`, которые будут указывать на начало и конец отрезка, в котором мы ищем число `x`. Изначально `left` будет равен 0, а `right` - длине массива минус 1.

Начинаем цикл, пока `left` не превысит `right`. Внутри цикла находим средний элемент отрезка с помощью формулы `mid = (left + right) // 2`. Сравниваем полученное значение с `x`. Если оно равно `x`, то число найдено, и мы выводим сообщение об этом и количество сравнений. Если значение меньше `x`, то сдвигаем `left` вправо, делая `left = mid + 1`. Если значение больше `x`, то сдвигаем `right` влево, делая `right = mid - 1`.

Если цикл завершился, и `left` стал больше `right`, значит число `x` не найдено в массиве, и мы выводим соответствующее сообщение.

Ниже приведен код, решающий данную задачу на языке Python:

import random

# Заполнение массива случайными числами
array = [random.randint(1, 10) for _ in range(10)]

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

# Вывод отсортированного массива
print("Массив:", array)

# Ввод числа x
x = int(input("Введите число x: "))

# Инициализация переменных для двоичного поиска
left = 0
right = len(array) - 1
comparisons = 0

# Двоичный поиск
while left <= right:
    mid = (left + right) // 2
    comparisons += 1

if array[mid] == x:
        print("Число", x, "найдено")
        print("Количество сравнений:", comparisons)
        break
    elif array[mid] < x:
        left = mid + 1
    else:
        right = mid - 1
else:
    print("Число", x, "не найдено")
    print("Количество сравнений:", comparisons)

В результате выполнения программы, будет выведено сообщение о том, найдено ли число `x` в массиве, а также количество сравнений, которое было произведено при поиске.