java - 二分查找算法的正确方法

标签 java binary-search

我刚刚了解了二分搜索算法并尝试实现它。我使用了一些测试用例,看起来效果很好。然而,当我检查 GeeksforGeeks 时,他们处理索引的方式有相当多的差异。任何人都可以阐明我的实现是否良好。如果没有,它怎么会失败?

这是我的代码:

static int binarySearch(int arr[], int i, int r, int x) {

    if(r > 1) {
        int middle = r/2;

        if(arr[middle] == x) {
            return middle;
        }

        if(arr[middle] > x) {
            return binarySearch(arr, i, middle, x);
        }else {
            return binarySearch(arr, middle, r+1, x);
        }
    }       

    return -1;
}

最佳答案

假设我们的函数将对子数组 arr[l..r] 进行二分搜索(包括的)。在这里,r - l + 1是这个子数组的长度,当它不是正数(或 r < l )时,我们没有有效的子数组,我们无法搜索任何内容,因此函数停止递归并返回 -1。

你知道,我们总是创建两个长度(几乎)相等的子数组。所以,middle = r/2不正确且 middle = (l + r) / 2是正确的。新的子数组是 arr[l..middle-1]arr[middle+1..r] 。我们在检查子数组的中间元素后对其进行划分,因此这两个子数组不应包含中间索引,如您所见。

现在,我们可以重写您的代码。

static int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int middle = (l + r) / 2; //int middle = l + (r - l) / 2; for avoiding integer overflow
        if(arr[middle] == x)
            return middle;
        if (arr[middle] > x)
            return binarySearch(arr, l, middle - 1, x);
        else
            return binarySearch(arr, middle + 1, r, x);
    }       
    return -1;
}

这是二分搜索算法的非递归版本。通常,它的工作速度会稍快一些。

static int binarySearch2(int arr[], int l, int r, int x) {
    while (r >= l) {
        int middle = (l + r) / 2; //int middle = l + (r - l) / 2; for avoiding integer overflow
        if (arr[middle] == x)
            return middle;
        if (arr[middle] > x)
            r = middle - 1;
        else
            l = middle + 1;
    }
    return -1;
}

在调用这些函数之前,不要忘记对数组进行排序。 假设n是给定数组的长度。 对于从 0 开始的数组,调用函数的正确形式是这样的:

binarySearch(arr, 0, n - 1, x);

binarySearch2(arr, 0, n - 1, x);

对于从 1 开始的数组,调用函数的正确形式是这样的:

binarySearch(arr, 1, n, x);

binarySearch2(arr, 1, n, x);

关于java - 二分查找算法的正确方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58127683/

相关文章:

java - 根据 DST 转换存储在 DB 中的时间

python - 二分查找元素的最低索引

c - 数组中的二分查找

java equal 和 == 混淆

java - Spring Boot @ManagedResource 组件在 Docker 中启动时在 VisualVM 中不可见,但可以在本地运行

java - 测试使用 Java Swing : best approach? 编码的应用程序 GUI

algorithm - 如何确定排序数组在哪个索引处旋转?

java - 安卓内存不足

c++ - 二进制搜索程序无法识别边界?

c++ - 二进制搜索没有返回正确的值