Основная проблема, которая мешает вам видеть рекурсию, состоит в том, что аргументы вашего метода - это просто массив и компаратор.Если бы вы передали начальный и конечный индексы (что обычно делали на более старом языке), вы бы увидели возможность рекурсии.
Я обычно не люблю выдавать псевдокод для таких вопросов, предпочитаявместо этого, чтобы дать вам подсказки относительно структуры и характера алгоритма.Однако вы не сможете соединить 2 + 2, когда ваши методы определены таким образом.Поэтому я собираюсь сделать здесь исключение:
Вместо этого (что у вас есть):
public static int binarySearch(Comparable[] objArray,Comparable item)
{
int lower=0;
int upper=objArray.length -1;
У вас есть это (это псевдокод, похожий на Java, очень упрощенный)и без проверки ошибок вам нужно проработать фактические детали синтаксиса):
public static int binarySearch(Comparable[] objArray,Comparable item)
{
return bSearch(objArray, item, 0, objArray.length -1);
....
private static int bSearch(Comparable[] objArray,Comparable item, int lower, int upper)
{
if( lower > upper /* not found */){ return -1; };
int pivot = ((int)((upper - lower) / 2)) + lower;
int cmp = objArray[pivot].compareTo(item);
if( cmp == 0 ){ return pivot; }
else if (cmp < 0 ){ return bSearch(objArray,item, lower, pivot - 1); }
else{ return bSearch(objArray,item, pivot+1, upper); }
}
Опять же, вам нужно проработать фактический синтаксис и проверку параметров, но кроме этого, это типичный псевдокод длярекурсивный бинарный поиск.Вы должны были это увидеть и поработать над этим до тошноты не позднее, чем на курсе второкурсников.
Рекурсия происходит следующим образом:
Если ваш массив отсортирован,и
Если вы начнете сравнение в середине, то есть стержень,
И сравнение не удастся,
Тогда
Вы знаете, что вам нужно искать только одну половину (либо верхнюю половину, если цель> разворот, либо нижнюю половину, если цель <разворот). </p>
Таким образом, вы берете половину, по которой собираетесь искать, и снова выполняете те же самые шаги на ней .Что может быть лучше, чем вызывать точно такой же алгоритм, точно такую же функцию только для этой части, для этого подмножества вашего ввода?
Это рекурсия.
Редактировать: Разработкав предыдущем примере, когда вы хотите / должны реализовать что-то рекурсивное в Java, лучше иметь утилитарный метод , который принимает структуру данных в целом (скажем, только массив и объект сравнения, как выв вашем примере).
Затем пусть вызовет внутренний метод, который выполняет рекурсию (и который должен иметь дело с передачей параметров). Причина в том, что ваши вызывающие программыне нужно передавать нижний и верхний индексы (так как они могут быть вычислены из объекта массива.)
В других языках нижнего уровня, таких как C, Pascal или Ada, вы иногда не можете вычислить такие аргументы и должныобъявите ваши рекурсивные функции с параметрами, явно переданными вашими вызывающими.
Поэтому, почему я разделил рекурсию вотдельная функция bSearch в приведенном выше псевдокоде.