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

lets say i have an array A in non-descending order like this

假设有一个非降序排列的数组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]

My question is: how to find the first occurence (index) of an element equal or greather (if 4 is not present) than 4?

我的问题是:如何找到与4相等或大于4的元素的第一个出现(索引)?

O(n) solution is easy, i would like to have something faster. Probably binary search, but have no idea how to modify it.

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

3 个解决方案

#1

This is a slightly modified binary search to compare with the previous element before returning. If there is a duplicate, you continue the binary search as expected, not serial search, so it's O(log(n)) independently on the structure of the sorted array (e.g. when many duplicates exist). It is written in Java.

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

*If the element does not present, I return the index of the next greater element, i.e. the index the key should be inserted if I had to put it in the array. I return a negative value as an indicator of "not found".

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

*The only exception for negative not-found value is when the key is the smallest and not-found, where you expect 0 (it doesn't have a negative). But, you can easily handle this special case to distinguish between found and not-found: e.g return the Integer.MIN_VALUE or -(array.length + 1) if -lo == 0.

*为负的未找到值的唯一例外是当键是最小的且未找到时，您期望的值为0(它没有负的值)。但是，您可以很容易地处理这个特殊情况，以区分找到的和没有找到的:e。g返回整数。MIN_VALUE或(数组。长度+ 1)如果-lo == 0。

*If the key is bigger than every array-value, you expect to return an index equal to array size (negative value again).

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

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

#2

Standard binary search:

标准二叉搜索:

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

This variation, changes marked with *:

这个变化，变化标记为*:

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

This will zero in on the leftmost incidence of target, or the point where target would go if it’s missing. Then just look around in that area to see what to return.

这将指向最左侧的目标，或者如果目标缺失，目标会去的地方。然后在那个区域四处看看，看看能返回什么。

#3

The following python code uses a simple binary search algorithm to find the upper value. Runtime O(log(n))

下面的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)]

#1