使用二进制搜索的多个键的最后索引?

时间:2023-01-14
本文介绍了使用二进制搜索的多个键的最后索引?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我在排序数组中有多次出现的键,我想对它们执行二进制搜索,正常的二进制搜索会为多次出现的键返回一些随机索引,而我想要最后一次出现的索引那个键.

i have multiple occurrences of a key in a sorted array, and i want to perform binary search on them, a normal binary search returns some random index for the key having multiple occurrences, where as i want the index of the last occurrence of that key.

int data[] = [1,2,3,4,4,4,4,5,5,6,6];
int key = 4;
int index = upperBoundBinarySearch(data, 0, data.length-1, key);

Index Returned = 6

推荐答案

好吧,特别感谢@Mattias,这个算法听起来不错.无论如何,我已经完成了自己的工作,这似乎我给出了更好的结果,但是如果有人可以帮助我衡量我的算法和@Mattias 的复杂性,或者任何人有更好的解决方案,欢迎.......无论如何,这是我为该问题找到的解决方案,

Well, thanks to all especially @Mattias, that algo sounds good. anyway i have done with my own, that seem me to give better result, but if some one can help me to measure out the complexity of both algos mine and @Mattias, or any one has some better solution, it welcome..... anyhow here is the solution i found for the problem,

int upperBound(int[] array,int lo, int hi, int key)
{
    int low = lo-1, high = hi;
    while (low+1 != high)
    {
        int mid = (low+high)>>>1;
        if (array[mid]> key) high=mid;
        else low=mid;
    }
    int p = low;
    if ( p >= hi || array[p] != key )
        p=-1;//no key found
    return p;
}

这是第一次出现,我也更新了其他类似的帖子 二分查找中的第一次出现

this is for first occurrence, i also update the same with one other similar post First occurrence in a binary search

int lowerBound(int[] array,int lo, int hi, int key)
{
    int low = lo-1, high = hi;
    while (low+1 != high)
    {
        int mid = (low+high)>>>1;
        if (array[mid]< key) low=mid;
        else high=mid;
    }
    int p = high;
    if ( p >= hi || array[p] != key )
        p=-1;//no key found
    return p;
}

这篇关于使用二进制搜索的多个键的最后索引?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持html5模板网!

上一篇:将包含二进制值的字符串转换为十六进制 下一篇:将二进制字符串转换为十六进制字符串 JAVA

相关文章

最新文章