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

Question

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

Suppose that you are given a sorted sequence of distinct integers {A1,A2,...An}, drawn from 1 to m where n < m. Give an O(lgN) algorithm to find an integer <= m that is not present in A. For full credit, find the smallest such integer.

一个排序序列，和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 的数字丢失，并且您搜索右半部分。