Заполнить массив случайными числами и отсортировать его. Ввести число X.
Используя двоичный поиск, определить, сколько чисел, равных X, находится в массиве.
Пример:
Массив:
1 4 7 3 9 2 4 5 2
После сортировки:
1 2 2 3 4 4 5 7 9
Введите число X:
4
Число 4 встречается 2 раз(а).
Пример:
Массив:
1 4 7 3 9 2 4 5 2
После сортировки:
1 2 2 3 4 4 5 7 9
Введите число X:
14
Число 14 не встречается.

Решение задачи:

1. Создание массива случайных чисел и его сортировка: Сначала нужно заполнить массив случайными числами, после чего его отсортировать.

2. Ввод числа X: Пользователь вводит число $X$, которое необходимо найти в массиве.

3. Двоичный поиск: Используем двоичный поиск для нахождения числа $X$ в массиве и подсчитываем количество его вхождений.

4. Вывод результата: Если $X$ найдено, выводим количество его вхождений. Если нет, сообщаем, что число не встречается.

Пример кода на Python:

python
import random
# 1. Генерация массива и его сортировка
n = 10  # Длина массива
array = [random.randint(1, 10) for _ in range(n)]  # Заполнение случайными числами от 1 до 10
array.sort()  # Сортировка массива
print("Отсортированный массив:", array)
# 2. Ввод числа X
x = int(input("Введите число X: "))
# 3. Реализация двоичного поиска
def binary_search_count(arr, target):
    def find_first(arr, target):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left
    def find_last(arr, target):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return right
    first = find_first(arr, target)
    last = find_last(arr, target)
    if first <= last:
        return last - first + 1
    else:
        return 0
# 4. Подсчет количества вхождений X
count = binary_search_count(array, x)
# 5. Вывод результата
if count > 0:
    print(f"Число {x} встречается {count} раз(а).")
else:
    print(f"Число {x} не встречается.")

Пояснение кода:

1. Генерация массива: Используется random.randint для создания массива случайных чисел.

2. Сортировка: Метод sort() упорядочивает массив по возрастанию.

3. Двоичный поиск:

   • Нахождение первого вхождения: Функция find_first определяет, где начинается последовательность чисел, равных $X$.
   • Нахождение последнего вхождения: Функция find_last определяет, где заканчивается последовательность чисел, равных $X$.
   • Количество вхождений вычисляется как разность между последним и первым индексами плюс 1.

4. Вывод результата: Если результат равен 0, значит, число $X$ отсутствует в массиве.

Пример работы программы:

Ввод:

less
Отсортированный массив: [1, 2, 2, 3, 4, 4, 5, 7, 9]
Введите число X: 4

Вывод:

scss
Число 4 встречается 2 раз(а).

Ввод:

less
Отсортированный массив: [1, 2, 2, 3, 4, 4, 5, 7, 9]
Введите число X: 14

Вывод:

Число 14 не встречается.