Получение StackOverflowError при попытке рекурсивного поиска числа с использованием метода двоичного поиска в массиве T - PullRequest
Новая
       7

Получение StackOverflowError при попытке рекурсивного поиска числа с использованием метода двоичного поиска в массиве T

0 голосов
/ 17 октября 2011

Привет, я использую метод двоичного поиска, чтобы найти число в массиве, и у меня возникает ошибка StackOverflow при поиске числа, отличного от среднего.

Вот мой код: 

public static  <T extends Comparable< ? super T>>
    int find(T [] a, T x, int low, int high){
    if(low>high)
        throw new IllegalArgumentException();
    int tmp = (high-low)/2;

    if(a[tmp].compareTo(x)==0)
        return tmp;
    else if(a[tmp].compareTo(x)>0)
        find(a,x,tmp,high);
    else if(a[tmp].compareTo(x)<0)
        find(a,x,low,tmp);
    return -1;
}

Кроме того, если я попытаюсь найти число в tmp, он вернет -1. Я чувствую, что что-то упустил, но не могу понять, что. Спасибо заранее!

Ответы [ 3 ]

2 голосов
/ 17 октября 2011

Вам нужно: 

else if(a[tmp].compareTo(x)>0)
    find(a,x,tmp - 1,high);
else if(a[tmp].compareTo(x)<0)
    find(a,x,low,tmp + 1);

В противном случае вы в конечном итоге будете рекурсивно вызывать функцию с теми же аргументами, когда у вас есть, например, low = 0 и high = 1. Дело в том, что вам не нужно снова смотреть на элемент на mid, потому что вы уже знаете, больше или меньше он по отношению к значению, которое вы пытаетесь найти.

Кроме того, вместо IllegalArgumentException вы должны вернуть -1, если high меньше low.

2 голосов
/ 17 октября 2011

Это проблема: 

if(a[tmp].compareTo(x)>0)
    find(a,x,tmp,high);
else if(a[tmp].compareTo(x)<0)
    find(a,x,low,tmp);

Вы должны использовать tmp + 1 в первом случае и tmp - 1 во втором. В противном случае, если у вас есть (скажем) low = 0, high = 1, вы потенциально будете в итоге постоянно звонить с теми же аргументами; tmp будет равен 0, и если x больше a[0], вы просто позвоните find(a, x, 0, 1) снова.

Во всяком случае, это мое внутреннее чувство. Вы должны действительно регистрировать то, что происходит с точки зрения используемых низких / высоких значений - я уверен, что вы увидите какое-то повторение, прежде чем оно заработает.

РЕДАКТИРОВАТЬ: Вы также получили сравнение раунд неправильно. a[tmp].compareTo(x) вернет значение меньше 0, если a[tmp] меньше x - т. Е. Вам следует искать позже в массиве, а не раньше.

РЕДАКТИРОВАТЬ: В настоящее время ваш код «выхода с -1» не работает - вы всегда будете возвращать -1, если a[tmp].compareTo(x) вернет ненулевое значение, которое не выше нуля и не ниже нуля. Я призываю вас найти такое целое число :) (Было бы так же, если бы сравнить, чтобы быть нестабильным, но это отдельная проблема ...)

Один из вариантов - определить, если high == low - в этот момент, если вы не нажали правильное значение, вы можете вернуть -1: 

int comparison = a[tmp].compareTo(x); // Let's just compare once...
if (comparison == 0) {
   return tmp;
}
// This was our last chance!
if (high == low) {
   return -1;
}
// If a[tmp] was lower than x, look later in the array. If it was higher than
// x, look earlier in the array.
return comparison < 0 ? find(a, x, tmp + 1, high) : find(a, x, low, tmp - 1);
1 голос
/ 17 октября 2011 
public static  <T extends Comparable< ? super T>>
    int find(T [] a, T x, int low, int high){
    if(low>high)
        throw new IllegalArgumentException();
    int tmp = (high+low)/2;//replaced - with + for average

    if(a[tmp].compareTo(x)==0)
        return tmp;
    else if(a[tmp].compareTo(x)>0)
        return find(a,x,tmp,high); //return the found index
    else if(a[tmp].compareTo(x)<0)
        return find(a,x,low,tmp);
    return -1;
}

если tmp - это среднее от высокого и низкого, вам нужно добавить их, а затем разделить на 2

также возвращает найденное значение при рекурсивном вызове

...