Using recursive algorithm for binary search

Question

Help me. I am a newbie to java and I am stuck in binary search recursion (stackoverflow error) and I can't find solution anywhere.

public class BinarySearch {
    public static int binAry (int ary[], int st, int lt, int val){
        if (st<=lt) {
            int mid = (st + (lt-st)) / 2;
            if (val > ary[mid]) {
                binAry(ary, mid+1, lt, val);
            }
            else if (val < ary[mid]) {
                binAry(ary, st, mid-1, val);
            }
            else{
                return mid;
            }
        }
        return -1;
    }
    public static void main (String[] args){
        BinarySearch bs = new BinarySearch();
        int [] numbers = {0,1,2,3,4,5};
        int x = 3;
        int pt = numbers.length;
        int p = bs.binAry(numbers, 0, pt-1, x);
        if (p == -1){
            System.out.println("Number not found.");
        }
        else{
            System.out.println("Number found at " + p);
        }
    }
}

Not sure this is the issue (probably not), but it will surface later, switch binAry(...) with return binAry(...) when you call it recursively. Otherwise, you will return mid when the element is the middle of original array, and -1 in all other cases. — amit
– amit, Commented May 20, 2020 at 6:31
Consider using names that will improve the readbilty of the code, other than st and lt — c0der
– c0der, Commented May 20, 2020 at 6:39
(st +lt -st) / 2 is always (lt) / 2;. I assume that is not what u meant. — c0der
– c0der, Commented May 20, 2020 at 6:41

A. Baena · Accepted Answer · 2020-05-21 14:12:05Z

For what I see, the problem is that (val > ary[mid]) will always evaluate to true. Always. Thus your code will enter an endless loop, which, ultimately, results in a StackOverFlow exception.

If you follow the value of the variables involved in your code to that point, you will notice that val never changes, being its value 3 since the beginning.

Also, int mid = (st + (lt-st)) / 2 is the same as lt/2 because st + (lt - st) = st - st + lt (do the test by assigning them whatever values you want). So even though you change the value of st in binAry(ary, mid+1, lt, val), it really has no effect. lt will always be numbers.length - 1 and mid will always be 5/2=2.

Add this code right below int mid = (st + (lt-st)) / 2 to check for yourself:

System.out.println("st="+st);    
System.out.println("lt="+lt);
System.out.println("mid="+mid);

Maybe if you explained what you want to do I would understand this a bit better and perhaps I'd be able to actually help find a solution.

Edit: Ok, after dedicating it a bit more time I found your error. Change the formula:

int mid = (st + (lt-st)) / 2  // This is wrong
int mid = st + (lt-st) / 2;  // This is ok, notice the parentheses

Collectives™ on Stack Overflow

Using recursive algorithm for binary search

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related