问题描述
这是由史蒂芬Skiena的算法设计手册第2版，第143页。
This is a homework exercise from Steven Skiena's "The algorithm design manual" 2nd edition, p 143.
假设你被赋予不同的整数排序序列 {A1，A2，...一个} ，从 1 到 M ，其中 N'LT;米。举一个 O（LGN）算法来找到一个整数＆LT; = M 不是present在 A 。对于完全学分制，找到最小的这样的整数。
有一个排序的序列，而 O（LGN）都表明二进制搜索算法。我能想到的唯一方法是通过从 1 号通过 M 运行，并为每个号码做一个二进制搜索，看是否存在按顺序 A 。但是，这意味着 O（mlgN），不是真的 O（LGN）。
A sorted sequence, and O(lgN) both suggest a binary search algorithm. The only way I could think of is to run through numbers from 1 through m, and for each number do a binary search to see if it exists in sequence A. But that means O(mlgN), not really O(lgN).
推荐答案
有一个小于 A [K] 失踪，当且仅当
There is an integer less than A[k] missing if and only if
A[k] > k
（使用1基于索引）。
(using 1-based indexing).
因此，要找到最小的失踪数字，二进制搜索。先从中间指数 M 。如果 A [M] GT;米，再没有什么比 A [M] 失踪，在左半搜索一些较小的。否则，如果 A [M] ==米，没有比 M 更小的缺失，你搜索右半部分。
So to find the smallest missing number, binary search. Start with the middle index m. If A[m] > m, then there is a number smaller than A[m] missing, search in the left half. Otherwise, if A[m] == m, there is no smaller number than m missing, and you search the right half.
这篇关于查找差距相邻数字的有序范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！