使用二進制搜索的多個鍵的最後索引？

Question

我有一個排序數組中的鍵的多次出現，我想對它們進行二分搜索，一個普通的二分搜索返回一些隨機索引爲有多個出現的鍵，其中，我想要的最後一次出現的索引那把鑰匙。

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 

Answer 1

好吧，多虧了所有@Mattias，算法聽起來不錯。無論如何，我已經完成了我自己的事情，似乎我給了更好的結果，但是如果有人能夠幫助我衡量算法和Mine @Mattias的複雜性，或者任何人有更好的解決方案，它都歡迎.... 。 總之這裏是解決方案，我發現這個問題，

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

這是首次發生的，我也有一個其他類似的帖子First occurrence in a binary search

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

Answer 2

想必你想要一個爲O（log N）解決方案？ （否則，你可能只是做一個線性搜索。）

在C++中，有一種可能性（超出幾種），是使用std::upper_bound。這會給你一個迭代器，它的第一個元素大於你所要求的，所以你需要檢查前一個元素。這的確是O（log N）。

我不知道Java是否提供這種標準庫方法。然而，upper_bound的僞代碼在上面的鏈接中給出，應該很容易重新實現。

Answer 3

在二分查找中，您將鍵與數組數據[i]的元素進行比較。爲了得到最後一個匹配索引，你應該改變你的比較函數，這樣即使密鑰等於data [i]並且也等於data [i + 1]，它也會給出不等式。

int upperBoundBinarySearch(int data[],int start, int end, int key) { 
    while(start < end) { 
    int middle = start + (end-start)/2; 
    if (data[middle] == key && (middle == end || data[middle+1] != key)) 
     return middle; 
    if (data[middle] > key) 
     end = middle; 
    else { 
     if (start == middle) 
     return start; 
     start = middle; 
    } 
    } 
    return start; 
} 

Answer 4

在this answer的Java實現找到第一發生的一個關鍵的。有一個comment關於如何改變這個以找到最後的發生，但建議導致無限循環。雖然這個想法聽起來很合理。

編輯：經過一番研究，我發現了一個neat solution on The Algo Blog。由於第一次找到的匹配不一定是需要的匹配，因此您需要跟蹤迄今爲止的「最佳」匹配。當您獲得一場比賽時，您將其存儲並繼續進行該比賽右側的二進制搜索（low = mid + 1）。

public static int binarySearch(int[] a, int key) { 
    return binarySearch(a, 0, a.length, key); 
} 

private static int binarySearch(int[] a, int fromIndex, int toIndex, 
     int key) { 
    int low = fromIndex; 
    int high = toIndex - 1; 
    int found = -1; 

    while (low <= high) { 
     int mid = (low + high) >>> 1; 
     int midVal = a[mid]; 

     if (midVal < key) { 
      low = mid + 1; 
     } else if (midVal > key) { 
      high = mid - 1; 
     } else { 
      found = mid; 
      // For last occurrence: 
      low = mid + 1; 
      // For first occurrence: 
      // high = mid - 1; 
     } 
    } 
    return found; 
} 

此更改保持O(log n)的複雜性。但是，實際性能取決於應用程序。當陣列的長度遠大於所尋找關鍵字的重複數量時，對最後一次出現的線性搜索可能會更快。雖然有很多重複，但這種修改的二進制搜索可能更可取。

Answer 5

當你找到鑰匙。而不是返回它在數組上進行順序搜索以獲得最後一個。這將是O（N）解決方案。