發現相鄰數字

Question

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

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

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

Answer 1

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

A[k] > k 

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

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