Znajdź pierwszą liczbę większą niż podana w niesortowanej sekwencji

Question

Biorąc pod uwagę sekwencję dodatnich liczb całkowitych i liczbę całkowitą M, zwracaj pierwszą liczbę w sekwencji, która jest większa niż M (lub -1, jeśli nie istnieje) .

przykład: Sekwencja = [2, 50, 8, 9, 1], K = 3 -> powrót = 50

O (log n) dla każdego zapytania wymagane (po przetwarzania wstępnego).

myślałem o BSTS, ale biorąc pod uwagę sekwencję rosnąco chciałbym uzyskać tylko długą drogę, która nie dałaby mi O (logn) czas ...

EDIT: Używane struktura powinna być również łatwa do modyfikacji, tzn. powinna istnieć możliwość zamiany znalezionego elementu na dany i powtórzenia wyszukiwania innego M (wszystko - oprócz preprocessingu - O (logn)). I oczywiście byłoby miło, gdybym mógł zmienić "pierwszy większy" na "pierwszy mniejszy" i nie musiał zmieniać zbyt wiele w algorytmie. A jeśli to pomoże, możemy założyć, że wszystkie liczby są pozytywne i nie ma powtórzeń.

Answer 1

Utwórz drugą tablicę (niech będzie to aux), gdzie dla każdego elementu i: aux[i] = max { arr[0],arr[1], ... ,arr[i]} (maksimum wszystkich elementów o indeksie j <= i w oryginalnej tablicy).

Łatwo zauważyć, że ta tablica jest sortowana według natury, a prosty binary search na aux przyniesie potrzebny indeks. (Łatwo jest uzyskać za pomocą wyszukiwania binarnego pierwszy element, który jest większy niż żądany element, jeśli element nie istnieje).

Złożoność czasowa to wstępne przetwarzanie O(n) (wykonywane tylko raz) i O(logn) dla zapytania.