binary search tree recursion without return statement on the function calls-CodePudding

I am learning binary search tree using recursion and I made the below mistake of not adding return in line X and Y as commented out below.

What difference does not having the return statement mean on the stack of the function call? Apologies if the query is very basic but I would like to clarify it here.

I thought not having the return statement on the function call will still work as it will find a match and return the value if it exists in the array.

Sample values passed to the function

   int found = searchRecursive(new int[]{0, 1, 21, 33, 45, 45, 61, 71, 72, 73},21);

        System.out.println(found);

Code

 private static int searchRecursive(int array[], int target) {
        int low = 0;
        int high = array.length -1;
        return binarySearch(array, low, high, target);
    }

   private static int binarySearch(int array[], int low, int high, int target){
        int mid = (low high)/2;
        if(array[mid] == target){
            return mid;
        }
        else if(array[mid]>target) {
            return binarySearch(array, low, mid - 1, target); //line X
        } else {
            return binarySearch(array, mid 1, high, target);  //line Y
        }
    }

So I had it as below and it found the value but ended up finally returning as -1 instead of 21

private static int binarySearch(int array[], int low, int high, int target){
        int mid = (low high)/2;
        if(array[mid] == target){
            return mid;
        }
        else if(array[mid]>target) {
            binarySearch(array, low, mid - 1, target); //line X
        } else {
            binarySearch(array, mid 1, high, target);  //line Y
        }
        return -1;
    }

CodePudding user response：

First you do not detect failure to find an element. In fact low and high may run out of bounds by 1.

private static int binarySearch(int array[], int low, int high, int target) {
    if (low > high) {
        return -1;
    }
    int mid = (low high)/2;
    if (array[mid] == target) {
        return mid;
    } else if (target < array[mid]) {
        return binarySearch(array, low, mid - 1, target); //line X
    } else {
        return binarySearch(array, mid   1, high, target);  //line Y
    }
}

If one return is dropped, but the compiler can find a final return, the result is that of a temporary result.

You could also move the bounds more clearly:

private static int binarySearch(int array[], int low, int high, int target) {
    if (low > high) {
        return -1;
    }
    int mid = (low high)/2;
    if (array[mid] == target) {
        return mid;
    }
    if (target < array[mid]) {
        high = mid - 1;
    } else {
        low = mid   1;
    }
    return binarySearch(array, low, high, target);
}

And hence the iterative (non-recursive) version is:

private static int binarySearch(int array[], int low, int high, int target) {
    while (low <= high) {
        int mid = (low high)/2;
        if (array[mid] == target) {
            return mid;
        }
        if (target < array[mid]) {
            high = mid - 1;
        } else {
            low = mid   1;
        }
    }
    return -1;
}