使用二进制搜索查找缺失的数字

Question

我正在读珍珠编程的书.

问题:给定一个顺序文件,其中包含最多40个随机顺序的32位整数,找到一个不在文件中的32位整数(并且必须至少有一个丢失).如果我们有几百字节的主内存和几个顺序文件,就必须解决这个问题.

解决方案:要将其设置为二进制搜索,我们必须定义范围,范围内元素的表示,以及确定范围的哪一半保存缺失整数的探测方法.我们如何做到这一点？

我们将使用已知包含至少一个缺失元素的整数序列作为范围,我们将通过包含其中所有整数的文件来表示范围.我们可以通过计算其中点上方和下方的元素来探测范围:上限或下限范围总共有半个元素.因为总范围缺少元素,所以较小的一半也必须具有mising元素.对于上述问题,这些是二进制搜索算法的大多数成分.

上面的文字是Jon Bently从编程珍珠书的版权.

以下链接提供了一些信息

"编程珍珠"二进制搜索帮助

我们如何使用二分搜索进行搜索,也没有按照上面链接中给出的示例进行搜索？请帮助我理解逻辑只有5个整数而不是百万个整数来理解逻辑.

Answer 1

您为什么不重新阅读“Programming Pearls”二分搜索帮助中的答案呢？它按照您的要求解释了 5 个整数的过程。
这个想法是，你解析每个列表，并根据第一位的值将其分成 2 个（这是二进制部分的来源）单独的列表。

即显示实际数字的二进制表示原始列表“”：001,010,110,000,100,011,101=>（分解为）
（我们删除第一位并将其附加到新列表的“名称”中）为了形成下面的每个列表，我们从上面的 列表“ 0
” 中获取以[0或1]开头的值：01,10,00,11（由列表“”的子集001,010,000,011组成删除第一位并将其附加到新列表的“名称”） 列表“ 1 ”：10,00,01（通过删除第一位并将其附加到列表“”的子集 110,100,101 形成新列表的“名称”）

现在依次取出结果列表之一并重复该过程：
列表“ 0 ”成为您的原始列表，您将其分解为
列表“0***0**”和
列表“0***1**”（粗体数字又是列表中被破坏的数字的 1 [剩余] 位）

继续下去，直到得到空列表为止。

逐步编辑
过程：
列表“”：001、010、110、000、100、011、101 =>
列表“0”：01、10、00、11（来自列表的子集 001、010、000、011 "") =>
列表 "00": 1, 0 (来自列表 "0" 的子集 01, 00) =>
列表 "000": 0 [最终结果] (来自列表 "00" 的子集 0)
列表"001": 1 [最终结果] (来自列表 "00" 的子集 1)
列表 "01": 0, 1 (来自列表 "0" 的子集 10, 11) =>
列表 "010": 0 [ [最终结果]（来自列表“01”的子集 0）
列表“011”：1 [最终结果]（来自列表“01”的子集 1）
列表“1”：10, 00, 01（来自子集 110，列表 "" 的 100, 101) =>
列表 "10": 0, 1 (来自列表 "1" 的子集 00, 01) =>
列表 "100": 0 [最终结果] (来自列表 "1" 的子集 0列表“10”）
列表“101”：1 [最终结果]（来自列表“10”的子集 1）
列表“11”：0（来自列表“1”的子集 10）=>
列表“110”： 0 [最终结果]（来自列表“11”的子集 0）
列表“111”：不存在[最终结果]（来自列表“11”的 子集EMPTY ）

这种方法的优点是，它可以让您找到集合中任意数量的缺失数字 - 即如果缺失多个数字。

PS AFAIR 对于完整范围内的1 个缺失数字，还有更优雅的 XOR 所有数字解决方案。