CODEWITHSUNDEEP
javasearchrecursionbinary
htkibar
htkibar

Reputation: 23

java.lang.StackOverflowError in Binary Search Algorithm

Could you guys please help me? I get the error :

Exception in thread "main" java.lang.StackOverflowError
    at binarysearch.search(binarysearch.java:22)
    at binarysearch.search(binarysearch.java:31)

(binarysearch.java:31 repeats like a dozen times). I have been trying to understand recursion but I guess I failed at somewhere.

public class binarysearch {
    static int[] arr = new int[100];

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        fill();
        if (search(31, arr, 1, 30)) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }

    public static void fill() {
        for(int i = 1; i < 30; i++) {
            arr[i] = i;
        }
    }

    public static boolean search(int value, int[] data, int start, int end) {
        int len = end - start + 1 ;
        int mid = (start + end) / 2;
        if (len == 1) {
            return false;
        } else {
            if (data[mid] == value) {
                return true;
            } else {
                if (data[mid] < value) {
                    return search(value, data, mid, end);
                } else {
                    return search(value, data, start, mid);
                }
            }
        }
    }

}

Upvotes: 2

Views: 2141

Answers (2)

Alexey Odintsov
Alexey Odintsov

Reputation: 1725

Try to change recursion calls to:

if (data[mid] < value) {
    return search(value, data, mid+1, end);
} else {
    return search(value, data, start, mid-1);
}

Upvotes: 1

Ethan Fang
Ethan Fang

Reputation: 1269

from search(31, arr, 1, 30) You will run into

1, 30

15, 30

22, 30

26, 30

28, 30

29, 30

29, 30

29, 30

....

And become infinite stackOverFlow

So you algorithm should be 

public static boolean search(int value, int[] data, int start, int end) {
    int len = end - start + 1 ;
    int mid = (start + end) / 2;
    if (len == 1) {
        return false;
    } else {
        if (data[mid] == value) {
            return true;
        } else {
            if (data[mid] < value) {
                return search(value, data, mid + 1, end);
            } else {
                return search(value, data, start, mid - 1);
            }
        }
    }
}

Upvotes: 1

Related Questions