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

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

标准二分查找：

left limit = left end of array
right limit = right end of array
look at middle
if middle == target: stop
else:
    set left or right to middle based on result of comparison
    loop

此变体，更改标记为 *：

left limit = left end of array
right limit = right end of array
look at middle
* if limits are close together: stop
* if middle == target and limits are not close together:
*    set right to middle
*    loop
else:
    set left or right to middle based on result of comparison
    loop

这会将目标最左侧的发生率或点归零如果目标丢失了，它会去哪里。然后环顾四周区看看有什么要return.

Answer 2

以下 python 代码使用简单的二进制搜索算法来查找上限值。运行时间 O(log(n))

def binary_search(array, target):
lower = 0
upper = len(array)
while lower < upper:
    x = lower + (upper - lower) // 2
    val = array[x]
    if target == val:
        return x
    elif target > val:
        if lower == x:
            break
        lower = x
    elif target < val:
        upper = x
return upper

# Test Array
arr = [0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 5, 4, 4, 6, 7, 8]
print arr[binary_search(arr, 5)]

Answer 3

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

*如果该元素不存在，我 return 下一个更大元素的索引，即如果我必须将它放入数组中，则应插入键的索引。我return一个负值作为"not found"的指标。

*negative not-found value 的唯一例外是当键最小且 not-found 时，您期望 0（它不是有负数）。但是，您可以轻松处理这种特殊情况以区分 found 和 not-found：例如 return Integer.MIN_VALUE 或 -(array.length + 1) if -lo == 0.

*如果键大于每个 array-value，您期望 return 索引等于数组大小（再次为负值）。

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

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

Find first occurence of specified element in an array

arrays

algorithm

binary-search