logo标签列表

使用二分查找查找缺失数字

c++algorithmbinary-search
6
我正在阅读编程珠玑的书。
问题：给定一个最多包含40亿个32位整数的顺序文件，以随机顺序排列，找到不在文件中的32位整数（并且必须至少有一个缺失）。如果我们只有几百字节的主内存和几个顺序文件，则必须解决此问题。
解决方案：为了将其设置为二分搜索，我们必须定义一个范围、范围内元素的表示方法以及一种探测方法，以确定范围的哪一半包含缺失的整数。我们该如何做？
我们将使用一个已知至少包含一个缺失元素的整数序列作为范围，并通过包含其中所有整数的文件来表示范围。关键是我们可以通过计算中点上方和下方的元素数量来探测范围：总范围的上半部分或下半部分最多只有一半的元素。因为总范围有一个缺失元素，所以较小的一半也必须有一个缺失元素。这些是上述问题的二分搜索算法的大部分要素。
以上文本版权归Jon Bently编写的《编程珠玑》一书所有。
以下链接提供了一些信息。

"编程珠玑" 二分查找帮助

我们如何使用二分查找来搜索密码，并且不跟随上面链接中给出的示例？请帮助我用只有5个整数而不是百万个整数来理解逻辑。

5个回答
3
请再阅读帖子"Programming Pearls" binary search help中的答案。它解释了你所问的5个整数的过程。
思路是解析每个列表，并根据第一个位中的值将其分成两个（这就是二进制部分的来源）独立的列表。

即显示实际数字的二进制表示

原始列表：“001, 010, 110, 000, 100, 011, 101” => (分成)
（我们删除第一位并将其附加到新列表的“名称”）
为形成下面每个列表，我们从上面的列表中取值开始[0或1]
列表“0”：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 [最终结果]（从列表“10”的子集0中获取）
列表“101”：1 [最终结果]（从列表“10”的子集1中获取）
列表“11”：0（从列表“1”的子集10中获取）=>
列表“110”：0 [最终结果]（从列表“11”的子集0中获取）
列表“111”：缺席 [最终结果]（从列表“11”的子集空中获取）

这种方法的优点是它可以让你找到集合中任何数量的缺失数字 - 即使有多个缺失。
顺便说一句，如果完整范围内只有一个缺失数字，甚至还有更优雅的解决方案，即对所有数字执行XOR运算。
请详细说明如何使用异或运算对所有数字进行操作？ - venkysmarty
1
XOR所有数字的方法依赖于1 XOR 0 = 0的结果。互补的数字将得到0，只有没有互补的数字将保留下来。 再次基于3位数字（该原理适用于任何位数）： 给定一个列表[如上所示]001、010、110、000、100、011、101=>001补充110（在3位中），因此001 ^ 110 => 0的结果... - Germann Arlington
1
@GermannArlington 你是不是想说 1 XOR 0 = 1 而不是 1 XOR 0 = 0？ - Yno
@GermannArlington 为什么第二遍要从列表0开始而不是列表1？ - Geek
1
@GermannArlington 是错误的。XOR代表“异或”，这意味着a XOR b仅在a为真或b为真时为真，而不是两者都为真。 - Yno
显示剩余5条评论
1

这里有一个简单的C语言解决方案，可以说明该技术。为了抽象掉任何繁琐的文件I/O细节，我假设存在以下三个函数：

  • unsigned long next_number (void) 从文件中读取一个数字并返回它。当再次调用时，将返回文件中的下一个数字，以此类推。当遇到文件结尾时的行为是未定义的。

  • int numbers_left (void) 如果还有更多可使用next_number()读取的数字，则返回true值；如果已经到达文件结尾，则返回false。

  • void return_to_start (void) 将读取位置倒回到文件开头，以便下一次调用next_number()返回文件中的第一个数字。

我还假设unsigned long至少有32位宽度，符合ANSI C实现的要求；现代C程序员可能更喜欢使用stdint.h中的uint32_t。

根据这些假设，以下是解决方案：
unsigned long count_numbers_in_range (unsigned long min, unsigned long max) {
    unsigned long count = 0;

    return_to_start();

    while ( numbers_left() ) {
        unsigned long num = next_number();
        if ( num >= min && num <= max ) {
            count++;
        }
    }
    return count;
}

unsigned long find_missing_number (void) {
    unsigned long min = 0, max = 0xFFFFFFFF;

    while ( min < max ) {
        unsigned long midpoint = min + (max - min) / 2;
        unsigned long count = count_numbers_in_range( min, midpoint );

        if ( count < midpoint - min + 1 ) {
            max = midpoint;  // at least one missing number below midpoint
        } else {
            min = midpoint;  // no missing numbers below midpoint, must be above
        }
    }
    return min;
}

需要注意的一点是，min + (max - min) / 2 是计算 min 和 max 平均值的安全方法；它不会因为中间值 溢出 而产生错误结果，而看似更简单的 (min + max) / 2 可能会。

此外，虽然使用递归解决这个问题可能很诱人，但我选择了迭代解决方案，原因有两个：首先，因为它（可以说）更清楚地显示了实际正在做什么，其次，因为任务是最小化内存使用，这包括堆栈在内。

最后，优化这段代码将变得容易，例如当count等于零时立即返回，通过在一次遍历中计算范围的两个半部分中的数字并选择缺失数字更多的那一个，甚至通过将二分搜索扩展为n-ary搜索（其中n > 2）以减少通行证数量。然而，为了使示例代码尽可能简单，我没有进行这样的优化。如果您愿意，可以尝试修改代码，使其最多只需要8次文件遍历而不是当前的32次。（提示：使用一个16元素数组。）

这真的是二分查找的一种形式吗？输入没有排序，因此您必须遍历所有N个元素以计算每个范围中的数字数量。 - Bob Templ
@BobTempl：这是在32位整数空间中进行的二分查找。我们不是在文件中寻找缺失的数字（这是无望的，因为根据定义，它不存在）；我们是在0到0xFFFFFFFF范围内寻找它。通过计算给定子范围与文件内容的交集中的数字数量，我们可以确定缺失的数字（如果有多个，则至少有一个）是否在该子范围内。 - Ilmari Karonen
啊，我明白了，那样就更有意义了。 - Bob Templ
1

这个想法是解决更简单的问题：

缺失值是否在范围[minVal，X]或（X，maxVal）中。 如果你知道这一点，你可以移动X并再次检查。

例如，你有3、4、1、5（2缺失）。 你知道minVal = 1，maxVal = 5。

  1. 范围= [1,5]，X = 3，在范围[1,3]中应该有3个整数和范围[4,5]中的2个整数。在范围[1,3]中只有2个整数，所以你正在寻找范围[1,3]
  2. 范围= [1,3]，X = 2。在范围[1,2]中只有1个值，所以你正在寻找范围[1,2]
  3. 范围= [1,2]，X = 1。在范围[2,2]中没有值，所以这就是你的答案。

编辑：一些伪C++代码：

minVal = 1, maxVal = 5; //choose correct values
while(minVal < maxVal){
    int X = (minVal + maxVal) / 2
    int leftNumber = how much in range [minVal, X]
    int rightNumber = how much in range [X + 1, maxVal]
    if(leftNumber < (X - minVal + 1))maxVal = X
    else minVal = X + 1
}
在编程中，floor((begin + end) / 2) 可以简写为 (begin + end) / 2。在 C++ 中，你可以直接使用 (begin + end) / 2。 - Ari
感谢您的解释。在https://dev59.com/6m445IYBdhLWcg3wJ298中，我们有000、001、110、100、111。提到在第一次遍历后，我们得到了000、001、110、100、111。然后我们看第二位。我理解在第一次遍历后如何再次获得相同的值。 - venkysmarty
第一次遍历后，我们知道缺失的数字的第一个位是0。因此第二次迭代检查第二位是0还是1。没有第一位为0和第二位为1的数。所有第一位是0的数字都有第二位是0，所以我们得到相同的值。 - Ari
我们如何快速选择“leftNumber”和“rightNumber”？如果你用for循环计算，每次猜测都需要O(n)操作。:-? - SpiXel
@arri，我们怎么知道第一次迭代后缺失的数字的第一位是0？抱歉问题有点多。 - venkysmarty
显示剩余2条评论
0
实际上，如果我们有从a到b的整数范围。例如：[a..b]。 在这个范围内，我们有b-a个整数。这意味着只有一个缺失。 而且如果只有一个缺失，我们可以仅使用单个循环计算结果。 首先，我们可以计算范围[a..b]中所有整数的总和，其等于：
sum = (a + b) * (b - a + 1) / 2

然后我们计算序列中所有整数的总和：

long sum1 = 0;
for (int i = 0; i < b - a; i++)
sum1 += arr[i];

那么我们可以通过这两个和的差来找到缺失元素：

long result = sum1 - sum;

0

当在第i位上看到2^31个零或者1时，那么你的答案在第i位上就是0或者1。（例如：在第5个二进制位置上有2^31个1，则答案在第5个二进制位置上为0）

C代码的第一版草稿：

uint32_t binaryHistogram[32], *list4BILLION, answer, placesChecked[32];
uint64_t limit = 4294967296;
uint32_t halfLimit = 4294967296/2;
int i, j, done

//General method to point to list since this detail is not important to the question.
list4BILLION = 0000000000h;


//Initialize array to zero. This array represents the number of 1s seen as you parse through the list
for(i=0;i<limit;i++)
{   
    binaryHistogram[i] = 0;
}

//Only sum up for first half of the 4 billion numbers
for(i=0;i<halfLimit;i++)
{
    for(j=0;j<32;j++)
    {
        binaryHistogram[j] += ((*list4BILLION) >> j);
    }
}

//Check each ith digit to see if all halfLimit values have been parsed
for(i=halfLimit;i<limit;i++)
{
    for(j=0;j<32;j++)
    {
        done = 1;   //Dont need to continue to the end if placesChecked are all 
        if(placesChecked[j] != 0) //Dont need to pass through the whole list
        {
            done = 0; //
            binaryHistogram[j] += ((*list4BILLION) >> j);
            if((binaryHistogram[j] > halfLimit)||(i - binaryHistogram[j] == halfLimit))
            {
                answer += (1 << j);
                placesChecked[j] = 1;
            }
        }
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接