下面是对已排序数组中的元素进行二分查找的代码:
#include<stdio.h>
int binarySearch(int *arr, int l, int r, int data)
{
if(l > r)
return -1;
int mid = l+(r-l)/2; //find the middle index
if(data < arr[mid]) {
return(binarySearch(arr, l, mid-1, data));
}
else if(data > arr[mid]) {
return(binarySearch(arr, mid+1, r, data));
}
else {
return mid;
}
}
int main()
{
int arr [] = {0 , 11, 22, 33, 44, 55, 66 };
int n = sizeof(arr)/sizeof(arr[0]);
int data = 22;
int index = binarySearch(arr, 0, n-1, data);
if( index != -1)
{
printf("%d" , index);
}
return 0;
}
如何使搜索稳定?当数组的元素重复时,我的搜索应该返回数组中数据第一次出现的索引。
我希望我修改后的代码作为输出生成:
input array is {1, 22, 22, 22}
output = 1,
input array is {1, 12, 15, 22, 22, 22, 22, 22, 22, 22, 55 ,66}
output = 3
我不知道该怎么做。
最佳答案
您可以将匹配条件从 arr[mid] == data
更改为更复杂的 arr[mid] == data && (mid == 0 || arr[ mid-1] != 数据)
。变化:
else {
return mid;
}
到:
else if (mid == 0 || arr[mid-1] != data) {
// note that arr[mid] == data is implied at this point
return mid;
}
else {
return(binarySearch(arr, l, mid, data));
}
如果数组中有大量搜索值,这仍然会给你 O(log(n)) 性能(与其他一些更简单的解决方案相比,在这种情况下会降低 O(n) 性能) ).您还保留了原始搜索的 O(1) 最佳情况:也就是说,可能会在没有发生任何递归的情况下找到结果。
请注意,它确实假设可以访问下 (l
) 边界之外的数组,前提是该边界不为 0,而原始代码没有做出这样的假设。在您发布的示例中,这不是问题。如果这是一个问题,您可以将原始绑定(bind)向下传递(例如 ol
,然后上面的 mid == 0
变为 mid == ol
),或者改为使用:
else if (mid == l) {
return mid;
}
else {
return(binarySearch(arr, l, mid - 1, data));
}
然而,后者失去了 O(1) 最佳情况。
关于c++ - 如何使存储数组的二进制搜索稳定,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37746887/