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;
}

}