我刚刚了解了二分搜索算法并尝试实现它。我使用了一些测试用例,看起来效果很好。然而,当我检查 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/