CODEWITHSUNDEEP
javaarraysrecursionstack-overflowbinary-search
randomizertech
randomizertech

Reputation: 2329

Getting StackOverflowError when trying to find a number recursively using binary search method in a T array

Hey there I'm using a binary search method to find a number in an array, and I'm getting a StackOverflow error when looking for a number other than the one in the middle.

Here is my code:

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

Also, if I try to look for a number under tmp, it returns -1. I feel like I'm missing something but can't figure out what. Thanks in advanced!

Upvotes: 0

Views: 329

Answers (3)

Jon Skeet
Jon Skeet

Reputation: 1502106

This is the problem:

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

You should be using tmp + 1 in the first case and tmp - 1 in the second. Otherwise if you've got (say) low = 0, high = 1 then you'll potentially end up perpetually calling with the same arguments; tmp will end up being 0, and if x is more than a[0] you'll just call find(a, x, 0, 1) again.

That's my gut feeling, anyway. You should really log what happens in terms of the low/high values being used - I'm sure you'll see some sort of repetition before it croaks.

EDIT: You've also got the comparison round the wrong way. a[tmp].compareTo(x) will return a value less than 0 if a[tmp] is less than x - i.e. you ought to look later in the array, not earlier.

EDIT: Currently your "exit with -1" code is broken - you'll only ever return -1 if a[tmp].compareTo(x) returns a non-zero value which is neither above zero nor below zero. I challenge you to find such an integer :) (It would also do it if compareTo were unstable, but that's a separate issue...)

One option is to detect if high == low - at that point, if you haven't hit the right value, you can return -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);

Upvotes: 2

ratchet freak
ratchet freak

Reputation: 48216

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

if tmp is the average of high and low you need to add them and then divide by 2

also return the found value on the recursive call

Upvotes: 1

Vivin Paliath
Vivin Paliath

Reputation: 95558

You need:

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

Otherwise you'll basically end up recursively calling the function with the same arguments when you have low = 0 and high = 1 for example. The thing is that you don't really need to look at the element at mid again because you already know if it is greater or smaller in relation to the value you are trying to find.

Also, instead of the IllegalArgumentException, you should return -1 if high is lesser than low.

Upvotes: 2

Related Questions