6

我正在阅读有关编程珍珠的书。

问题：给定一个包含最多 40 亿个随机顺序的 32 位整数的顺序文件，找到一个不在文件中的 32 位整数（并且必须至少缺少一个）。如果我们有几百字节的主存和几个顺序文件，则必须解决这个问题。

解决方案：要将其设置为二分搜索，我们必须定义一个范围、范围内元素的表示形式以及确定范围的哪一半包含缺失整数的探测方法。我们如何做到这一点？

我们将使用已知包含至少一个缺失元素的整数序列作为范围，并且我们将通过包含其中所有整数的文件来表示范围。洞察力是，我们可以通过计算其中点上方和下方的元素来探测一个范围：上限或下限在整个范围中最多有一半元素。因为整个范围有一个缺失的元素，较小的一半也必须有一个缺失的元素。这些是针对上述问题的二分搜索算法的大部分成分。

以上文字是乔恩·本特利（Jon Bently）从编程珍珠书中获得的版权。

以下链接提供了一些信息

《Programming Pearls》二分查找帮助

我们如何通过使用二分搜索而不遵循上面链接中给出的示例进行搜索？请帮助我理解逻辑，只用 5 个整数而不是百万整数来理解逻辑。

4

5 回答 5

3

为什么不重新阅读“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、001、010、100、011、101 =>
列表“0”：01、10、00、11（来自列表的子集001、010、000、011 "") =>
List "00": 1, 0 (来自 List "0" 的子集 01, 00) =>
List "000": 0 [最终结果] (来自 List "00" 的子集 0)
List "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”：不存在[最终结果]（来自列表的子集EMPTY ” 11")

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

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

于 2012-09-07T09:08:44.433 回答
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 程序员可能更喜欢使用uint32_tfrom stdint.h。

鉴于这些假设，以下是解决方案：

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平均值的安全方法；由于像看似简单的可能那样溢出中间值，它不会产生虚假结果。minmax(min + max) / 2

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

最后，很容易优化此代码，例如，一旦count等于 0 就返回，通过一次计算范围的两半中的数字并选择具有更多缺失数字的数字，或者甚至将二分搜索扩展到n元搜索一些n > 2 以减少通过次数。但是，为了使示例代码尽可能简单，我没有进行此类优化。如果您愿意，您可能想尝试修改代码，使其最多需要 8 次遍历文件，而不是当前的 32 次。（提示：使用 16 元素数组。）

于 2012-09-07T11:11:27.223 回答
1

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

是 [minVal, X] 或 (X, maxVal) 范围内的缺失值。如果您知道这一点，您可以移动 X 并再次检查。

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

  1. Range = [1, 5], X = 3，在[1, 3]范围内应该有3个整数，在[4, 5]范围内应该有2个整数。[1, 3] 范围内只有 2 个，因此您正在查看 [1, 3] 范围内
  2. Range = [1, 3], X = 2。范围 [1, 2] 中只有 1 个值，因此您正在查看范围 [1, 2]
  3. Range = [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
}
于 2012-09-07T09:08:10.007 回答
0

当您在第 i 位看到 2^31 个零或一时，那么您的答案在第 i 位有一个或零。（例如：第 5 个二进制位置的 2^31 个表示答案在第 5 个二进制位置为零。

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;
            }
        }
    }
}
于 2014-05-31T23:26:18.330 回答
0

实际上，如果我们有从 a 到 b 的整数范围。示例：[a..b]。在这个范围内，我们有 ba 整数。这意味着，只缺少一个。如果只缺少一个，我们可以只使用一个周期来计算结果。首先，我们可以计算范围 [a..b] 中所有整数的总和，它等于：

sum = (a + b) * (b - a + 1) / 2

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

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

然后我们可以找到缺失元素作为这两个和的差：

长结果 = sum1 - sum;

于 2012-09-07T11:35:24.670 回答