在未排序的序列中查找大於給定值的第一個數字

Question

給定一個正整數序列和一個整數M，返回序列中大於M的第一個數字（如果不存在則返回-1） 。

示例：序列= [2，50，8,9，1]，M = 3 - >返回= 50

O（log n）的所需（預處理之後）每個查詢。

我想過BSTS的，但考慮到的遞增序列我會得到的只是一個長的路徑，這不會給我O（LOGN）時間...

編輯：二手結構也應該是容易修改，即應該可以用找到的元素替換找到的元素，然後重複搜索另一個M（除了預處理-O（logn））之外的所有內容。當然，如果我可以將'first first'更改爲'first small'並且不必在算法中改變太多，那就會很好。如果有幫助，我們可以假設所有數字都是正數，並且沒有重複。

Answer 1

創建第二個數組（其數值爲aux），其中每個元素i：aux[i] = max { arr[0],arr[1], ... ,arr[i]}（原始數組中索引爲j <= i的所有元素的最大值）。

很容易看出這個數組是按性質排序的，aux上的簡單binary search將產生所需的索引。 （如果元素不存在，使用二元搜索可以很容易地得到大於請求元素的第一個元素）。

時間複雜度爲O(n)預處理（僅完成一次）和O(logn)每個查詢。