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

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

此答案中的Java实现查找第一次出现的键.有一个评论关于如何可以改变,找到最后出现,但在一个无限循环的建议结果.不过,这个想法看似合理.

编辑:经过一些研究,我在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)复杂性.实际上,性能取决于应用程序.当阵列的长度远大于所寻找的密钥的重复量时,对最后一次出现的线性搜索可能更快.但是当存在大量重复时,这种修改后的二进制搜索可能更可取.