在相邻数字的有序范围内找到间隙

Question

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

假设你得到一个不同整数的排序序列{A1,A2,...An}，从1到m哪里n < m。给出一个O(lgN)算法来找到一个<= m在 中不存在的整数A。对于完整的信用，找到最小的这样的整数。

排序的序列，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缺失更小的数字，你搜索右半部分。