0

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

Проблема где-то в двоичном поиске, прошу помочь и объяснить ошибку.

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

}

3
  • возьмите карандаш и лист бумаги. Придумайте пример данных - не слишком простой (чтобы весь код исполнялся), но и не слишком сложный (чтобы можно было его сделать вручную). Пройдите по вашему коду шаг за шагом, записывая значения пременных. Очень скоро Вы сами обнаружите ошибку.
    – user176262
    6 окт 2017 в 13:18
  • 1
    Что-то я не припомню чтобы в двоичном поиске был цикл for (int j = 0; j < arr.length; j++), автоматически увеличивающий сложность алгоритма до O(n) (не говоря уж про while внутри for). Откуда взялся for?
    – Regent
    6 окт 2017 в 13:21
  • Regent, это уже были танцы с бубном. Изначально for не было. 6 окт 2017 в 13:24

1 ответ 1

1

Ошибок куча

  1. Зачем нужен этот цикл?

    for (int j = 0; j < arr.length; j++) {
    
  2. Из этого

    int k = (L + R) / 2;
    if (k == search) {
    

k - индекс текущего проверяемого числа. И сравнивается с самим числом. Бред.

3.

break

Вышли из while цикла for продолжает крутиться

Итого, должно быть, что-то типа такого

int nX = -1;
int L = 0;
int R = arr.length - 1;
while (L <= R) {
    int k = (L + R) / 2;
    if (arr[k] == search) {
        nX = arr[k];
        break;
    }
    else if (arr[k] < search) {
        R = k - 1;
    }
    else if (arr[k] > search) {
        L = k + 1;
    }
}

if (nX == -1) {
    System.out.println("Искомого числа нет в массиве");
} else {
    System.out.println("Искомое число было найдено и равно " + nX);
}

Адекватность проверки if (nX == -1) оставляю на Вашей совести. Я бы не был бы так уверен, что в массиве не встретится -1

Эта строка

System.out.println("Искомое число было найдено и равно " + nX);

легко заменяется на такую

System.out.println("Искомое число было найдено и равно " + search);

Может логичнее выводить индекс найденного числа?

1
  • 1
    Спасибо, очень помогли! На счет ошибок: 1-я отмеченная Вами ошибка, была добавлена уже после, как крайность и я заранее понимал что так нельзя. Так что - полностью моя ошибка, хоть и осознанная. 2-я отмеченная Вами ошибка, я теперь понял свой основной косяк. Изначально у меня был такой же код, как предоставили Вы, единственное были различия в наименовании переменных, но суть та же. Проблема была в том, что я индекс текущего числа обозвал по одному, а в массиве называл по другому и не заметил этого, а ошибку не понимал. В общем, спасибо Вам еще раз! Добра Вам и удачи! 6 окт 2017 в 13:34

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.