整数的递归二进制搜索

Question

我尝试过使用递归实现二分查找的分治法。它的代码可以在下面看到。我认为当程序为运行时，我会出现堆栈溢出。如果有人设法找到解决方案，我将不胜感激发生这种情况的原因。

public class binarySearch{
    public static void main(String[] arguments){
        int[] array = new int[]{1,2,3,4,5,6,7,8,9};
        int findNum = binSearch(array, 9, 0, array.length-1);
    }

    public static int binSearch(int[] array, int searchNum, int left, int right){
        int foundIndex = 0;
        boolean found = false;
        int mid = (right+left)/2;
        if(array[mid] == searchNum){
            found = true;
            foundIndex = mid;
        }
        else if(array[mid] > searchNum){
            right = mid;
            binSearch(array, searchNum, left, right);
        }
        else if(array[mid] < searchNum){
            left = mid;
            binSearch(array, searchNum, left, right);
        }

        if(found = true){
            return foundIndex;
        }
        else{
            return -1;
        }
    }
}

Answer 1

您正在调用 binSearch 但从未 return 调用该调用的值。我认为您试图将 found 视为 C 中的静态变量，但在 Java 中没有这样的事情。即使你在另一个stackframe中修改它，你当前stackframe中的值仍然会保持false.

更好的方法是使用尾递归并直接 return 结果。

public static int binSearch(int[] array, int searchNum, int left, int right){
    if (left == right) 
        return -1;
    int mid = (right + left) >>> 1;
    if(array[mid] == searchNum) 
        return mid;
    else if(array[mid] > searchNum) 
        return binSearch(array, searchNum, left, mid);
    else 
        return binSearch(array, searchNum, mid + 1, right);
}

你可以这样调用方法（right应该是独占的）

int findNum = binSearch(array, -1, 0, array.length);

编辑：在阅读 Debapriya Biswas 的之后，我将行 int mid = (right + left) / 2; 更改为 int mid = (right + left) >>> 1; 以避免在 right + left 大于 int 的最大值。

Answer 2

你的实现逻辑错误，导致你的代码陷入无限递归。正确的代码应该如下 -

public class binarySearch{
    public static void main(String[] arguments){
        int[] array = new int[]{1,2,3,4,5,6,7,8,9};
        int findNum = binSearch(array, 9, 0, array.length-1);
    }

    public static int binSearch(int[] array, int searchNum, int left, int right){
        if(left>right)
            return -1; // We have now tried the full binary search and unable to find the element
        int mid = (right+left)/2;
        if(array[mid] == searchNum){
             return mid;
        }
        else if(array[mid] > searchNum)
            return binSearch(array, searchNum, left, mid-1); // <-- Here you were calling 
                                                             //binSearch(array, searchNum, left, right); which made your code go into infinite recursion

        else if(array[mid] < searchNum)
            return binSearch(array, searchNum, mid+1, right); //<-- you were calling 
                                                              //binSearch(array, searchNum, left, right); which made your code go into infinite recursion           
    }
}

如果在数组中找到元素，上面的代码将 return 索引，否则它将 return -1。您还会注意到我直接 return 进行递归调用，例如 - return binSearch(array, searchNum, mid+1, right); 而不仅仅是调用 - binSearch(array, searchNum, left, right);

希望对您有所帮助！

Answer 3

到目前为止发布的所有解决方案在计算 mid.The 潜伏在 JDK 中超过 20 年的相同错误时都存在整数溢出问题 https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

int binarySearch(int arr[],int searchNum,int left, int right)
    {
        if (right >= left) {
            int mid = (left+right)>>>1; 
            if (arr[mid] == searchNum)
                return mid;
            if (arr[mid] > searchNum)
                return binarySearch(arr, left,mid - 1, searchNum);

            return binarySearch(arr, mid + 1, right, searchNum);
        }
        return -1;
    }

整数的递归二进制搜索

Recursive Binary Search for Integers

java

stack-overflow

recursion

binary-search