Java中二分查找的递归实现

Question

我正在尝试用Java递归实现二分搜索。

我想出了这个，但它只返回-1。但是，我不明白为什么无论我使用什么数组，这都是唯一的结果。

数组示例：数组 int = {1, 6, 7, 9, 11 , 16};

调用示例：recursiveBinarySearch(array, 7, array.length, 0);

public static int recursiveBinarySearch(int array[], int key, int high, int low) {
    
    int mid = (high + low) / 2;
    int middleNumber = array[mid];
        
    if (key == middleNumber )
        return mid; 
    else if (low > high)
        return -1;
        
    else {
        if (middleNumber > key) {
            high = mid - 1; 
            recursiveBinarySearch(array, key, high, low);
        }
        
        else {
            low = mid + 1; 
            recursiveBinarySearch(array, key, high, low);
        }
        
    }
    
    return -1;
    
}

Answer 1

您需要从每个递归调用返回值并删除最后一个

return -1

语句

int[] array = {1, 6, 7, 9, 11 , 16};
for (int target : new int[] {3, 7}) {
   int index = recursiveBinarySearch(array, target, array.length, 0);
   System.out.println(index >= 0 ? array[index] : "Target not found!");
}    

打印

Target not found!
7

public static int recursiveBinarySearch(int array[], int key, int high, int low) {
    
    int mid = (high + low) / 2;
    int middleNumber = array[mid];
        
    if (key == middleNumber )
        return mid;
    else if (low > high)
        return -1;
        
    else {
        if (middleNumber > key) {
            high = mid - 1; 
            return recursiveBinarySearch(array, key, high, low);
        }
        
        else {
            low = mid + 1; 
            return recursiveBinarySearch(array, key, high, low);
        }    
    }
}