递归调用不会因二分查找而终止

Question

有人可以告诉我我做错了什么吗？当我的递归调用看到“return mid”时，它不会终止，但它会继续执行剩余的条件。

public class BinSearch {

    public static int binSearch(int[] a, int key, int low, int high){        
        
        if (low >= high){
            System.out.println("Low = High");
            return -1;
        }       
        int mid = low + ((high - low)/2);
        //System.out.println("Value of Mid for low:"+low+", high:"+high+" is:"+mid);
        if (a[mid] == key){            
            System.out.println("Value of mid is:"+a[mid]);
            return mid;
        } 
        else if (a[mid] < key){
            binSearch(a, key, mid+1, high);
        }
        else {
            binSearch(a, key, low, high)
        }               
        System.out.println("I am somehow out of the loop!");
        return -1;
    }


    public static void main (String[] args){
        System.out.println("Hello World");
        int[] arr = {1, 6, 9, 13, 22, 27, 29 , 38, 49, 50, 61, 72};
        int key = 22;
        int high = arr.length;
        int response = binSearch(arr, key, 0, high);
        System.out.println("The response is"+ response);

    }
}

Answer 1

看起来你得到了 mid 的值，但它没有保存也没有使用，所以每次它到达 binSearch 的末尾并输出 -1 。您可能希望使 binSearch 成为二分搜索的辅助函数，并且可以返回 binSearch(a, key, low, high)，而不是递归调用 binSearch。另外，您可能希望通过返回 binSearch(a, key, low, mid-1) 来返回数组的下半部分，而不是返回 binSearch(a, key, low, high)。当 low 大于 high 时，该函数应返回 -1。您的代码看起来不错，希望有所帮助！

公共类 BinSearch {

public static int Search(int[] a, int key){
  return binSearch(a, key, 0, a.length-1);
}

public static int binSearch(int[] a, int key, int low, int high){        //make this the helper function
    
    if (low > high){
        System.out.println("Low = High");
        return -1;
    }       
    int mid = low + ((high - low)/2);
    //System.out.println("Value of Mid for low:"+low+", high:"+high+" is:"+mid);
    if (a[mid] == key){            
        System.out.println("Value of mid is:"+a[mid]);
        return mid;
    } 
    else if (a[mid] < key){
      //add return
        return binSearch(a, key, mid+1, high);
    }
    else {
      //add return and return for lower part of array
      return binSearch(a, key, low, mid-1);
        //return binSearch(a, key, low, high);
    }               
    /*System.out.println("I am somehow out of the loop!");
    return -1;*/
}

public static void main (String[] args){
    System.out.println("Hello World");
    int[] arr = {1, 6, 9, 13, 22, 27, 29 , 38, 49, 50, 61, 72};
    int key = 22;
    int high = arr.length;
    int response = Search(arr, key);
  //binSearch(arr, key, 0, high);
    System.out.println("The response is"+ response);
}

}