0

I've written this binary search algorithm based on recursion but I'm unable to understand the reason for the error.

    // Only a sorted array must be entered for binary search to work
    public int binarySearch(int searchFor, int[] inArray, int from, int to){
        if (to >= from){
            int mid = (to-from)/2 + from;
            
            if (inArray[mid] == searchFor){
                return inArray[mid];
            } else if (inArray[mid] < searchFor){
                binarySearch(searchFor, inArray, ++mid, to);
            } else if (inArray[mid] > searchFor){
                binarySearch(searchFor, inArray, from, ++mid);
            }
        }
        return -1;
    }

Exception in thread "main" java.lang.StackOverflowError

at search.binarySearch(search.java:24)
at search.binarySearch(search.java:24)
at search.binarySearch(search.java:24)
at search.binarySearch(search.java:24)
Improve this question
5
  • 6
    I think you need add return inside else if calls Commented Jan 2, 2021 at 16:03
  • 1
    Check this example is very similar to your code. Example. As mentioned @VedantTerkar you miss the word return in both "else if" instructions. Commented Jan 2, 2021 at 16:10
  • 1
    Add the input values to understand the problem Commented Jan 2, 2021 at 16:19
  • 2
    Besides the missing returns, you also miscalculate the upper bound when you go left: You want mid - 1 here. (And I think you should return the index, mid, instead of the value inArray[mid], which you already know.) Commented Jan 2, 2021 at 17:09
  • 1
    And you should have a way to deal with the fact that the element was not found. Commented Jan 2, 2021 at 17:16

2 Answers 2

Reset to default
1

A few issues and remarks:

  • In the last case, the value ++mid is wrong as argument for binarySearch. That value should be one less than mid in that case.

  • I would also vote against the use of ++mid or --mid here, as that suggests that it is important that mid changes value, which is not needed. You should just pass mid+1 in the first case, and mid-1 in the second.

  • binarySearch returns an int, but when your code calls it recursively it doesn't do anything with that return value.

    You should return that value. So:

                } else if (inArray[mid] < searchFor){
                return binarySearch(searchFor, inArray, mid+1, to);
//              ^^^^^^                                  ^^^^^
            } else if (inArray[mid] > searchFor){
                return binarySearch(searchFor, inArray, from, mid-1);
//              ^^^^^^                                        ^^^^^
            }

  • The expression (to-from)/2 + from is a verbose way of doing (from+to)/2...

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

3 Comments

(The expression (from + to) / 2 could overflow for large numbers. Using (to - from) / 2 + from prevents overflow. Probably not a concern here.)
Expression (to-from)/2 + from is a defensive measure against integer overflow :)
Yes, that would be a necessary precaution when dealing with arrays of at least 2³⁰ ints, i.e. 4GB.
1

Apart from adding return to the recursive calls of binarySearch, there are a couple of flaws in the logic:

  • mid should be decremented to catch values in the left part:
    return binarySearch(searchFor, inArray, from, --mid);
  • there should be a check for valid mid, from, to values to fit inside the input array

Thus, the method should look as:

public static int binarySearch(int searchFor, int[] inArray, int from, int to) {
        if (to >= from && from > -1 && to <= inArray.length) {
            int mid = (to-from)/2 + from;
            
            if (mid >= inArray.length) {
                return -1;
            }
            
            // System.out.printf("from=%d to=%d mid=%d val=%d%n", from, to, mid, inArray[mid]); // debug print
            if (inArray[mid] == searchFor) {
                return inArray[mid];
            } else if (inArray[mid] < searchFor){
                return binarySearch(searchFor, inArray, ++mid, to);
            } else {
                return binarySearch(searchFor, inArray, from, --mid);
            }
        }
        return -1;
    }
}

Tests:

public static int binarySearch(int searchFor, int... inArray) {
    System.out.printf("Searching for %d in %s%n", searchFor, Arrays.toString(inArray));
    return binarySearch(searchFor, inArray, 0, inArray.length);
}

System.out.println(binarySearch(10));
    System.out.println(binarySearch(10, 10));
    System.out.println(binarySearch(10, 1));
    System.out.println(binarySearch(10, 0, 1, 5, 8, 10, 21));
    System.out.println(binarySearch( 0, 0, 1, 5, 8, 10, 21));
    System.out.println(binarySearch(21, 0, 1, 5, 8, 10, 21));
    
    System.out.println(binarySearch(10, 0, 1, 3, 5, 8, 10, 21));
    System.out.println(binarySearch( 0, 0, 1, 5, 8, 10, 15, 21));
    System.out.println(binarySearch(21, 0, 1, 5, 8, 10, 16, 21));
    
    System.out.println(binarySearch(30, 0, 1, 5, 8, 10, 21));
    System.out.println(binarySearch(-1, 0, 1, 5, 8, 10, 21));
    System.out.println(binarySearch(7, 0, 1, 5, 8, 10, 21));

Output:

Searching for 10 in []
-1
Searching for 10 in [10]
10
Searching for 10 in [1]
-1
Searching for 10 in [0, 1, 5, 8, 10, 21]
10
Searching for 0 in [0, 1, 5, 8, 10, 21]
0
Searching for 21 in [0, 1, 5, 8, 10, 21]
21
Searching for 10 in [0, 1, 3, 5, 8, 10, 21]
10
Searching for 0 in [0, 1, 5, 8, 10, 15, 21]
0
Searching for 21 in [0, 1, 5, 8, 10, 16, 21]
21
Searching for 30 in [0, 1, 5, 8, 10, 21]
-1
Searching for -1 in [0, 1, 5, 8, 10, 21]
-1
Searching for 7 in [0, 1, 5, 8, 10, 21]
-1
Improve this answer

Comments