java.lang.StackOverflowError in Binary Search Algorithm

Question

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

}

StackOverflowError ===== Infinite (or very deep ) recursion... Debug your code.. you will get the error.. — TheLostMind
– TheLostMind, Commented Jan 15, 2014 at 12:53
Thanks for the help. I am trying to learn about recursion so that's why I wrote it myself ^^ — htkibar
– htkibar, Commented Jan 15, 2014 at 15:27

Ethan Fang · Accepted Answer · 2014-01-15 13:02:57Z

1

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

1, 30

15, 30

22, 30

26, 30

28, 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);
            }
        }
    }
}

answered Jan 15, 2014 at 13:02

Ethan Fang

1,26910 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

htkibar Over a year ago

Off by one eh? Thank you for walkthrough and all ^^

Alexey Odintsov · Accepted Answer · 2014-01-15 13:03:56Z

1

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

answered Jan 15, 2014 at 13:03

Alexey Odintsov

1,72512 silver badges13 bronze badges

Collectives™ on Stack Overflow

java.lang.StackOverflowError in Binary Search Algorithm

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related