arrays - 查找数组中指定元素的第一次出现

Question

假设我有一个非降序排列的数组A

A = [0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9, 10, 11, 12, 500, 600]

我的问题是:如何找到等于或大于(如果 4 不存在)大于 4 的元素的第一次出现(索引)？

O(n) 解决方案很简单，我想要更快的东西。可能是二进制搜索，但不知道如何修改它。

Answer 1

这是一个稍微修改过的二分搜索，在返回之前与前一个元素进行比较。如果有重复项，您将按预期继续二进制搜索，而不是串行搜索，因此它的 O(log(n)) 独立于排序数组的结构(例如，当存在许多重复项时)。它是用 Java 编写的。

*如果该元素不存在，我将返回下一个更大元素的索引，即如果我必须将它放入数组中，则应插入该键的索引。我返回一个负值作为“未找到”的指示符。

*negative not-found value 的唯一异常(exception)是当键最小且未找到时，您期望为 0(它没有负数)。但是，您可以轻松处理这种特殊情况以区分找到和未找到:例如返回 Integer.MIN_VALUE 或 -(array.length + 1) 如果 -lo == 0。

*如果键大于每个数组值，您期望返回一个等于数组大小的索引(再次为负值)。

public static int indexOf(int[] a, int key) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if      (key < a[mid]) hi = mid - 1;
        else if (key > a[mid]) lo = mid + 1;
        else if (mid == 0 || key != a[mid-1]) return mid;
        else hi = mid - 1; //we have a duplicate, go left
    }
    //not present; show index of next greater element
    //OR array.length if bigger than every existing element
    return -lo;
}