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

2022-01-09 00:00:00 algorithm binary search c++ java

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

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;
}

相关文章