發現相鄰數字

的排序範圍內的差距這是史蒂芬Skiena的「算法設計手冊」第二版一門功課演習，第143發現相鄰數字

假設你被賦予不同的整數排序序列{A1,A2,...An}，從1到m，其中n < m。給出一個O(lgN)算法，以找到不存在於A中的整數<= m。要獲得完整信用，請找到最小的此類整數。

一個有序序列，並O(lgN)都表明二進制搜索算法。我能想到的唯一方法是運行1到m之間的數字，並對每個數字進行二進制搜索，看它是否存在於序列A中。但這意味着O(mlgN)，而不是O(lgN)。

2012-12-10 R Chen

這是一個古老的謎題。提示：Sum（1..N）= N（N + 1）/ 2。 –

@DiegoBasch這個提示是針對不同的問題。在這個問題中，可能有多個缺少的數字。提示這個問題：如果沒有數字丟失，那麼'A [i] = i'。 –

我正在考慮這個方法，我的提示也適用於這個問題。 –

有一個整數小於A[k]當且僅當

A[k] > k

（使用基於1的索引）丟失。

所以要找到最小的缺失數，二進制搜索。從中間索引m開始。如果A[m] > m，則有一個小於A[m]的數字缺失，在左半部分搜索。否則，如果A[m] == m，沒有比m丟失更少的數字，並且您搜索右邊的一半。

2012-12-10 01:32:24

回答