整数的递归二进制搜索[重复]。

Question

这个问题在这里已经有了答案:

什么是StackOverflowError？ (14个答案)

封闭 19天前.

我试着用递归实现了二进制搜索的分而治之技术。下面可以看到它的代码。我想当程序运行时，我得到了堆栈溢出。如果有人能找到解决方法，我将非常感激为什么会发生这种情况。

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

你的实现逻辑是错误的，因此你的代码会运行到无限递归。正确的代码应该如下----------。

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           
    }
}

上面的代码如果在数组中找到了元素，就会返回索引，否则就会返回-1。你也会注意到，我直接返回递归调用，比如--。return binSearch(array, searchNum, mid+1, right);而不只是打电话喜欢 - binSearch(array, searchNum, left, right);

希望能帮到你!

Answer 2

目前发布的所有解决方案都存在计算mid时整数溢出的问题，同样的bug在JDK中潜伏了20多年。https:/ai.googleblog.com200606extra-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;
    }

Answer 3

你在叫 binSearch 但从不返回该调用的值。我想你是想把 found 在C语言中是一个静态变量，但在Java中没有这样的东西。即使你在另一个堆栈框架中修改了它，你当前堆栈框架中的值仍然会保持在 false.

更好的方法是使用尾部递归，直接返回结果。

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.