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

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）解决方案。