Бинарный метод рекурсии в Java не работает - PullRequest
Новая
       11

Бинарный метод рекурсии в Java не работает

0 голосов
/ 12 октября 2019

Это код. Пожалуйста, скажите мне, что я делаю неправильно Так что это программа на Java, которая выполняет бинарный поиск с использованием рекурсивного метода. Требуется массив и переменная поиска.

Я знаю, что что-то не так, но я не уверен, что это такое. Что я делаю не так и как это изменить? 

public static int binary(int arr[], int target) {
    int start = 0;
    int end = arr.length;
    int mid = (start+end)/2;

    if(end<start) {
        return -1;
    }

    if (arr[mid] == target) {
        return mid;
    }
    else if (arr[mid] > target) {
        start = mid + 1;
        int[] newArr = new int[end];
        for(int i=start;i<end;i++) {
            int j=0;
            newArr[0] = arr[i];
            j++;
        }
        return binary(newArr,target);
    } else {
        end = mid - 1;
        int[] newArr = new int[end];
        for(int i=start;i<end;i++) {
            newArr[i] = arr[i];
        }
        return binary(newArr,target);
    }
}

1 Ответ

1 голос
/ 12 октября 2019

Я укажу, что копируя части массива в новый меньший массив, вы снижаете ценность выполнения бинарного поиска. Хорошо реализованный бинарный поиск выполняется за O (log (n)), тогда как то, что вы здесь делаете, выполняется за O (n). Вместо этого, если вы хотите реализовать бинарный поиск рекурсивно, вам нужно просто передать исходный массив и верхнюю и нижнюю границы, которые вы сейчас рассматриваете.

При этом причина того, что ваш код не является '• Даже получение правильного ответа, а тем более быстрого его получения, связано с несколькими различными ошибками.

  • Предполагается, что ваш массив предварительно отсортирован в порядке возрастания (двоичный поиск не может работать привсе, если ваш массив не отсортирован по порядку), тогда у вас есть случай, когда средняя точка больше, чем цель, и случай, когда средняя точка меньше, чем цель, обратная.
  • Ваш код для копирования верхнего уровняиз массива имеет несколько проблем. Напоминаем, что если вы копируете части своего массива, то вы неправильно выполняете бинарный поиск. Тем не менее, ваш код копирования массива для этого случая записывает только в начальный индекс нового массива [0] вместо того, чтобы идти по новому массиву и старому массиву одновременно.
...