Заполнить массив случайными числами и отсортировать его ввести число x. Используя двоичный поиск, определить, есть ли в массиве число , равно x. Если такого числа нет, вывести число, ближайшее к x.на языке python желательно с комментариями на каждую строчку кода,

ИбрагимЛе ИбрагимЛе    3   07.04.2021 13:03    166

Ответы
oksanadavidienozexft oksanadavidienozexft  18.01.2024 09:10
Конечно, я могу помочь вам с решением задачи!

Возьмем на вооружение следующий алгоритм:

1. Создадим функцию `binary_search`, которая будет выполнять двоичный поиск в массиве. Она будет принимать на вход отсортированный массив `arr`, число `x`, а также начальный и конечный индексы для поиска внутри массива.
2. Внутри функции `binary_search` добавим переменную `mid`, которая будет хранить индекс среднего элемента в текущей части массива.
3. Проверим условие, если начальный индекс стал больше или равен конечному индексу, то значит элемент не найден. В этом случае мы будем выводить число, ближайшее к `x` из двух соседних элементов.
4. Если условие не выполнилось, то найдем средний индекс элемента.
5. Проверим условие, если элемент с найденным индексом равен искомому числу `x`, то мы вернем `True`, так как элемент найден.
6 . Проверим условие, если элемент с найденным индексом меньше искомого числа `x`, то мы продолжим поиск в правой половине массива, вызвав рекурсивно функцию `binary_search` с обновленными значениями начального индекса (равного `mid + 1`) и конечного индекса.
7. Если условие не выполнилось, то мы продолжим поиск в левой половине массива, вызвав рекурсивно функцию `binary_search` также с обновленными значениями начального индекса (равного `low`) и конечного индекса (равного `mid - 1`).
8. В основной программе сделаем следующее:
- Создадим пустой массив `nums` и заполним его случайными числами с помощью модуля `random` в заданном диапазоне.
- Отсортируем массив с помощью метода `sort()`.
- Выведем отсортированный массив на экран.
- Ввод числа `x` с клавиатуры.
- Вызываем функцию `binary_search` с отсортированным массивом `nums`, числом `x` и начальным и конечным индексами.
- Если результат функции `binary_search` равен `True`, то выводим сообщение, что число `x` найдено в массиве.
- Если результат функции `binary_search` равен `False`, то выводим ближайшее число к `x`, используя индексы найденных соседних элементов.

Вот код с комментариями на каждую строку:

```python
import random

def binary_search(arr, x, low, high):
if low <= high:
mid = (low + high) // 2
if arr[mid] == x:
return True
elif arr[mid] < x:
return binary_search(arr, x, mid + 1, high)
else:
return binary_search(arr, x, low, mid - 1)
else:
return False

# Основная программа
nums = []

for _ in range(10): # Заполняем массив 10 случайными числами
nums.append(random.randint(1, 100))

nums.sort() # Сортируем массив

print("Отсортированный массив:", nums)

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

if binary_search(nums, x, 0, len(nums) - 1):
print("Число", x, "найдено в массиве.")
else:
closest_num = min(nums, key=lambda num: abs(num - x))
print("В массиве нет числа", x, ". Ближайшее число:", closest_num)
```

Надеюсь, это решение поможет вам решить задачу! Если у вас возникнут еще вопросы, не стесняйтесь задавать их.
ПОКАЗАТЬ ОТВЕТЫ
Другие вопросы по теме Информатика