問(wèn)題描述

我在排序數(shù)組中有多次出現(xiàn)的鍵，我想對(duì)它們執(zhí)行二進(jìn)制搜索，正常的二進(jìn)制搜索會(huì)為多次出現(xiàn)的鍵返回一些隨機(jī)索引，而我想要最后一次出現(xiàn)的索引那個(gè)鍵.

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，這個(gè)算法聽(tīng)起來(lái)不錯(cuò).無(wú)論如何，我已經(jīng)完成了自己的工作，這似乎我給出了更好的結(jié)果，但是如果有人可以幫助我衡量我的算法和@Mattias 的復(fù)雜性，或者任何人有更好的解決方案，歡迎.......無(wú)論如何，這是我為該問(wèn)題找到的解決方案，

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

這是第一次出現(xiàn)，我也更新了其他類似的帖子 二分查找中的第一次出現(xiàn)

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

這篇關(guān)于使用二進(jìn)制搜索的多個(gè)鍵的最后索引?的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！