問題描述

我在排序數組中有多次出現的鍵，我想對它們執行二進制搜索，正常的二進制搜索會為多次出現的鍵返回一些隨機索引，而我想要最后一次出現的索引那個鍵.

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模板網！