Заполнить массив случайными числами и отсортировать его. Ввести число 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 не встречается.

Предыдущий
вопрос Следующий
вопрос

import java.util.Arrays
import java.util.Random
import java.util.Scanner;

public class Main
public static void main(String[] args)
Random random = new Random()
Scanner scanner = new Scanner(System.in);

System.out.print("Введите размер массива: ")
int size = scanner.nextInt()
int[] array = new int[size]
for (int i = 0; i < size; i++)
array[i] = random.nextInt(10)

System.out.println("Исходный массив:")
System.out.println(Arrays.toString(array))
Arrays.sort(array)
System.out.println("Отсортированный массив:")
System.out.println(Arrays.toString(array))
System.out.print("Введите число X: ")
int x = scanner.nextInt()
int count = binarySearchCount(array, x)
if (count > 0)
System.out.println("Число " + x + " встречается " + count + " раз(а).")
} else
System.out.println("Число " + x + " не встречается.")

public static int binarySearchCount(int[] array, int target)
int first = firstOccurrence(array, target)
int last = lastOccurrence(array, target)
if (first == -1 || last == -1)
return 0

return last - first + 1

public static int firstOccurrence(int[] array, int target)
int low = 0
int high = array.length - 1
int result = -1
while (low <= high)
int mid = low + (high - low) / 2
if (array[mid] == target)
result = mid
high = mid - 1
} else if (array[mid] < target)
low = mid + 1
} else
high = mid - 1


return result

public static int lastOccurrence(int[] array, int target)
int low = 0
int high = array.length - 1
int result = -1
while (low <= high)
int mid = low + (high - low) / 2
if (array[mid] == target)
result = mid
low = mid + 1
} else if (array[mid] < target)
low = mid + 1
} else
high = mid - 1


return result
}

}