二进制搜索功能不起作用

Question

我是 Java 的新手，刚开始学习一些简单的数据结构和算法。我一直在尝试实现二进制搜索功能，但我不断收到堆栈溢出错误，而且我不知道它来自哪里。

public class BinarySearch {
    public static void main (String[]args){
        BinarySearch bs = new BinarySearch();

    int array [] = {1, 8, 6, 91, 52, 74, 5, 9};
    int length = array.length;
    bs.sort(array, 0, length-1);
    bs.print(array);
    System.out.println();
    System.out.println(bs.binarySearch(array, 0, length-1, 5));
}

public int binarySearch(int array [], int low, int high, int desired){
    int pivot = array[(low+high)/2];
    if(desired<pivot){
        binarySearch(array,low,pivot, desired);
    }else if(desired>pivot){
        binarySearch(array, pivot+1, high, desired);
    }else {
        return (low+high)/2;
    }
    // if element not present in array
    return -1;
}

Answer 1

当我运行时，我得到一个 indexoutofboundsexception 因为在这些行中：

int pivot = array[(low+high)/2];
if(desired<pivot){
   binarySearch(array,low,pivot, desired);
}

您将 pivot 作为最高价，可以是 array 中的任何数字。在此摘录的第一行中，您调用 high + low 的索引，它可以是 array 中的任何数字加上您最初作为 low 传递的任何数字。所以在这个例子中你可以调用 array 的 0 + 92 索引。

至于Whosebug是在这一行：

if(desired<pivot){
     binarySearch(array,low,pivot, desired);
}

在这里你在递归调用中传递了完全相同的参数，所以如果它进入 if 循环的这个分支，它将继续调用递归调用直到太多的递归调用进入堆栈并且出现堆栈溢出错误

Answer 2

BinarySearch 当数组本身已经排序（按顺序）时使用，这是 BinarySearch 的基础，你已经完成了 sorting 部分。

但是您的解决方案中存在两个明显的问题：

你的问题主要在于：pivot，你这里使用的元素作为index；
包括 mid 应该忽略的地方，因为 if (desired < pivot)；

此外，你应该尝试使用low + (high-low) / 2获取中间索引（当数组大小足够大时low + high会炸毁int）然后得到pivot = array[mid] 以避免整数溢出，这也是获得中间索引的更好做法。

public class BinarySearchBasic {
    public static void main(String[] args) {
        BinarySearchBasic bs = new BinarySearchBasic();

        int array[] = {1, 8, 6, 91, 52, 74, 5, 9};
        int length = array.length;
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
        System.out.println();
        System.out.println(bs.binarySearch(array, 0, length - 1, 5)); // miss;
        System.out.println(bs.binarySearch(array, 0, length - 1, 8)); // hit!
    }

    public int binarySearch(int array[], int low, int high, int desired) {
        int mid = low + (high - low) /2;
        int pivot = array[mid]; // get the middle element;
        if (desired < pivot) {
            binarySearch(array, low, mid - 1, desired); // since it's already smaller, use mid - 1 directly;
        } else if (desired > pivot) {
            binarySearch(array, mid + 1, high, desired); // same reason, use mid + 1 directly to skip mid;
        } else {
            return mid; // bingo!
        }
        return -1; // not found;
    }
}

输出：

[1, 5, 6, 8, 9, 52, 74, 91]

-1
3

Answer 3

您没有基本案例。递归需要一个基本案例来知道何时停止递归。无限递归的结果是WhosebugException，因为你一直在调用，但没有返回。你将进入无限递归。二分查找的基本情况是 hi 小于 lo。

您还想将左调用更改为从 low 变为 m-1 而不是枢转，因为您的边界在两端都包含在内。

您还使用了枢轴 VALUE 作为您的索引！而不是中间 INDEX:

binarySearch(array, low, pivot-1, desired);

应该是：

binarySearch(array, low, m-1, desired);

方法：

public int binarySearch(int array [], int low, int high, int desired) {

    // Not found
    if (high < low) 
        return -1;

    // Middle index
    int m = low + (high - low) / 2;

    // Middle value
    int pivot = array[m];

    if (desired < pivot)
        binarySearch(array, low, m-1, desired);

    else if (desired > pivot) 
        binarySearch(array, m+1, high, desired);

    else 
        return m;

}

Answer 4

您的代码有几个问题。

您没有return递归调用的结果。添加 return.

if(desired<pivot){
    return binarySearch(...);
}else if(desired>pivot){
    return binarySearch(...);
}

不要将您正在检查的索引与您正在检查的枢轴值混在一起。计算指标，单独使用。此外，在反复出现低位时，使用 index - 1 而不是 index 作为 high，以将当前指数从未来的考虑中剔除。

int index = (low+high)/2;
int pivot = array[index];

if(desired<pivot){
    return binarySearch(array,low,index - 1, desired);
}else if(desired>pivot){
    return binarySearch(array, index+1, high, desired);
}else {
    return index;
}

如果您的低值大于高值，则未找到该值。那是你的基本情况，而不是底部的 returning -1（现在无论如何都是无法访问的代码，因为 return 以上的每个逻辑分支都已经是一个值）。将其置于当前 if.
上方
```
int index = (low+high)/2;
int pivot = array[index];
if (low > high)
    return -1;
if ...
```

假设您的 sort 工作正常，上述更改应该 return 元素的索引正确，或者 -1 如果找不到。

二进制搜索功能不起作用

Binary search function not working

java

binary-search