Задание: Создать массив случайных чисел, отсортировать его по убыванию, а затем провести двоичный поиск числа в данном массиве. Число вводит пользователь с клавиатуры.
Проблема где-то в двоичном поиске, прошу помочь и объяснить ошибку.
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
Random rand = new Random();
int arr[] = new int[20];
for (int i = 0; i < arr.length; i++) { //Заполнение массива
arr[i] = rand.nextInt(50);
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
for (int i = 0; i < arr.length - 1; i++) {
for (int j = arr.length - 2; j >= i; j--) { //Cортировка по убыванию
if (arr[j] < arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for (int j = 0; j < arr.length; j++) { //Вывод отсортированого массива
System.out.print(arr[j] + " ");
}
System.out.println();
System.out.println("Введите число для поиска");
int search = s.nextInt();
int nX = -1;
int L = 0;
int R = arr.length - 1;
for (int j = 0; j < arr.length; j++) {
while (L <= R) {
int k = (L + R) / 2;
if (k == search) {
nX = k;
break;
}
else if (k < search) {
R = k - 1;
}
else if (k > search) {
L = k + 1;
}
}
}
if (nX == -1) {
System.out.println("Искомого числа нет в массиве");
} else {
System.out.println("Искомое число было найдено и равно " + nX);
}
}
}
for (int j = 0; j < arr.length; j++)
, автоматически увеличивающий сложность алгоритма доO(n)
(не говоря уж проwhile
внутриfor
). Откуда взялсяfor
?