使用二进制搜索查找多个条目

Question

我使用标准二进制搜索来快速返回排序列表中的单个对象(相对于可排序属性).

现在我需要修改搜索,以便返回所有匹配列表条目.我该怎么做才能做到最好？

Answer 1

好吧,当列表被排序时,您感兴趣的所有条目都是连续的.这意味着您需要找到与找到的项目相等的第一个项目,从二进制搜索生成的索引向后查找.关于最后一项也一样.

你可以简单地从找到的索引向后移动,但是这样解决方案可能和O(n)一样慢,如果有很多项目等于找到的项目.所以你应该更好地使用指数搜索:当你找到更多相等的项目时,你的跳跃加倍.这样你的整个搜索仍然是O(log n).

Answer 2

首先让我们回想起天真的二进制搜索代码片段:

int bin_search(int arr[], int key, int low, int high)
{
    if (low > high)
        return -1;

    int mid = low + ((high - low) >> 1);

    if (arr[mid] == key) return mid;
    if (arr[mid] > key)
        return bin_search(arr, key, low, mid - 1);
    else
        return bin_search(arr, key, mid + 1, high);
}

引自Prof.Skiena:假设我们删除了等式测试if(s [middle] == key)return(middle); 从上面的实现中,并在每次不成功的搜索时返回索引低而不是-1.现在所有搜索都不成功,因为没有相等测试.每当将密钥与相同的数组元素进行比较时,搜索将进入右半部分,最终终止于右边界.在反转二进制比较的方向之后重复搜索将引导我们到左边界.每次搜索都需要O(lgn)时间,因此无论块的大小如何,我们都可以以对数时间计算出现次数.

因此,我们需要两轮binary_search来查找lower_bound(找到不小于KEY的第一个数字)和upper_bound(找到大于KEY的第一个数字).

int lower_bound(int arr[], int key, int low, int high)
{
    if (low > high)
        //return -1;
        return low;

    int mid = low + ((high - low) >> 1);
    //if (arr[mid] == key) return mid;

    //Attention here, we go left for lower_bound when meeting equal values
    if (arr[mid] >= key) 
        return lower_bound(arr, key, low, mid - 1);
    else
        return lower_bound(arr, key, mid + 1, high);
}

int upper_bound(int arr[], int key, int low, int high)
{
    if (low > high)
        //return -1;
        return low;

    int mid = low + ((high - low) >> 1);
    //if (arr[mid] == key) return mid;

    //Attention here, we go right for upper_bound when meeting equal values
    if (arr[mid] > key) 
        return upper_bound(arr, key, low, mid - 1);
    else
        return upper_bound(arr, key, mid + 1, high);
}

希望它有用:)

Answer 3

如果我正在关注您的问题,那么您有一个对象列表,为了进行比较,它们看起来像{1,2,2,3,4,5,5,5,6,7,8,8,9}.正常搜索5将触及一个比较为5的对象,但是你想要全部获取它们,是吗？

在那种情况下,我建议一个标准的二进制搜索,在着陆到匹配元素时,开始向左看,直到它停止匹配,然后再向右(从第一个匹配)再次直到它停止匹配.

请注意,您使用的任何数据结构都不会覆盖与之相比的元素!

或者,考虑使用一种结构,该结构存储与该位置中的桶相比较的元素.