Найти первое вхождение указанного элемента в массиве

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.

* Если элемент отсутствует, я возвращаю индекс следующего большего элемента, то есть индекс должен быть вставлен в ключ, если бы мне пришлось помещать его в массив. Я возвращаю отрицательное значение как показатель «не найден».

* Единственное исключение для отрицательное не найденное значение - это когда ключ наименьший и не найден, где вы ожидаете 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; 
} 

Answer 2

Стандартный бинарный поиск:

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 

Это нуль на крайнем левом падении цели, или точка , где цель будет идти, если он отсутствует. Затем просто осмотрите область , чтобы увидеть, что вернуть.

Answer 3

Следующий код python использует простой алгоритм бинарного поиска, чтобы найти верхнее значение. Runtime 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)]