I can't understand why the function will not stop and return the mid, but it keeps going down to the return -1.

public class BinarySearch {

    public static int BS(int[] arr, int target, int first, int last) {
        if(first != last) {
            int mid = first   (last - first)/2;
            System.out.println("arr[mid] = " arr[mid]);
            if(arr[mid] != target) {
                if(target < arr[mid]) {
                    last = mid - 1;
                    System.out.println("last is " last);
                    BS(arr, target, first, last);
                }else {
                    first = mid   1;
                    BS(arr, target, first, last);
                }
            }else {
                System.out.println("Found!");
                return mid;
            }
            System.out.println("test");
        }
    
        if(arr[first] == target) return first;
        System.out.println("Not found!");
        return -1;
    }
    
    public static void main(String[] args) {
        int[] test = {0,1,2,4,6,7,9,10};
        int result = BS(test, 7, 0, test.length-1);
        System.out.println(result);

    }

}

CodePudding user response：

When you have return mid 3 calls deep it is 2nd BS that gets that value and since it does not use the value it is lost. Instead it continues to the 3 last lines of the function since that is what the code tells it to do. Unless the element to be found is the first element you never return it.

Recursive functions are not treated special. Their argument, local variables and state are different is not shared and a return only returns that one call and does not affect the other ongoing calls.

You could replace each recursive call with a similar function BS1 that calls BS2 etc. that produces the same code at each level and it will work the same. Then there will be no recursive call, but it will work the same way. A return in BS4 will not affect BS3 except for its returned value it should use. One return in BS3 does not cancel the calls BS2, BS1 as they are waiting for an answer to continue their flow. With a return BS2(arr, target, first, last); that continued flow is to return the value that the call to BS2 returns.

Your first calls that returns is System.out.println. If it worked that the first return was the final result then its value would be the result of your logic.