c++ - 如何使存储数组的二进制搜索稳定

Question

下面是对已排序数组中的元素进行二分查找的代码:

#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

我不知道该怎么做。

Answer 1

您可以将匹配条件从 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) 最佳情况。