algorithm - 在相邻数字的有序范围内查找间隙

Question

这是 Steven Skiena 的“算法设计手册”第 2 版，第 143 页的家庭作业。

假设给定一个不同整数的排序序列，{A1,A2,...An}从where抽取。给出一个算法来找到一个不存在于 中的整数。对于完整的信用，找到最小的这样的整数。1mn < mO(lgN)<= mA

排序后的序列，O(lgN)两者都建议使用二进制搜索算法。我能想到的唯一方法是遍历从1through中的数字m，并对每个数字进行二分搜索以查看它是否按顺序存在A。但这意味着O(mlgN)，不是真的O(lgN)。

Answer 1

有一个小于A[k]缺失的整数当且仅当

A[k] > k

（使用从 1 开始的索引）。

所以要找到最小的缺失数，二分查找。从中间索引开始m。如果A[m] > m，则有一个小于A[m]缺失的数，在左半部分搜索。否则，如果A[m] == m，没有比m缺失更小的数字，则搜索右半部分。