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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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