跳转至内容
  • 版块
  • 最新
  • 标签
  • 热门
  • Online Tools
  • 用户
  • 群组
折叠
品牌标识

D2Learn Forums

  1. 主页
  2. Blogs | 博客
  3. Maxwell1905's Blog
  4. 分享一种通过二分法快速查找数组中缺失数字的方法

分享一种通过二分法快速查找数组中缺失数字的方法

已定时 已固定 已锁定 已移动 Maxwell1905's Blog
blogs
3 帖子 2 发布者 18 浏览
  • 从旧到新
  • 从新到旧
  • 最多赞同
登录后回复
此主题已被删除。只有拥有主题管理权限的用户可以查看。
  • sky-littlestarS 离线
    sky-littlestarS 离线
    sky-littlestar
    编写于 最后由 编辑
    #1

    最近在看《编程珠玑》提升自己的C语言编程能力,书中的第二章提出了一个有趣的问题。
    该问题的描述如下:给定一个最多包含40亿个随机排列的32位整数的顺序文件,找出一个不在文件中的32位整数(在文件中至少缺失一个这样的数--为什么?)。在具有足够内存的情况下,如何解决该问题?如果有几个外部的“临时”文件可用,但是仅有几百字节,又该如何解决问题。
    对于为啥文件会确实一个32位的数,这个是显而易见的,我们知道2^32次方是4,294,967,296这个数大于40亿,所以40亿个数是无法完全包含32位整数的全部的。至于,这里有40亿个数,我们怎么找到究竟缺失了哪几个数,这是这个章节考察的重点。我们能不能通过遍历的办法,通过一个基准值然后对比40亿个数,如果能比对成功就证明存在,如果比对不成功,就证明这个数是当前文件所确实的,这个方法当然是可以的,但是在实施是完全不现实的。每比对一个数,就要遍历40亿次(注意,文中指出数据是无序的),所以基本上都要大范围遍历,还要遍历40亿次,这对计算机的性能消耗是巨大的,计算时间也是不可想象的。能不能缩少遍历次数呢,书本提到了位图的方法,通过创建一个大的数组,每个数组的每个位,1代表该数存在,0代表该数不存在,这样,遍历一次即可把位图填满,然后我们再遍历一次位图,看看哪个是0,即可知道究竟是缺失了哪一个数,那这个方法确实可以大大提升计算效率,但是,我们的问题还有一个限制条件,即是内存是有限的,我们很难一次创建一个很大的位图,快速完成遍历。通过理论计算可知,4,294,967,296/8=536,870,912,创建一个完整位图,需要超过500MB的内存,书中最后提出了一个二分搜索的方法。
    位图法的原理如下:
    1、首先我们先创建一个位图(本文以32位为例子说明),随后将其整个位图初始化为0:
    代码如下,比较简单
    首先宏定义,
    #define N 31
    #define BITWORD 8
    uint8_t test_array[N / BITWORD + 1] = { 0 };
    b151ec93-4a90-4a7d-bcb9-8853d330babd-image.png

    随后,我们可以设计位图操作函数,分别是:
    void set_bit(uint8_t* array, uint8_t num);//将位图相关位置置1
    void set_bit(uint8_t* array, uint8_t num)
    {
    array[num >> 3] |= (1 << (num & 0x7));
    }
    void clear_bit(uint8_t* array, uint8_t num);//将位图相关位置置0
    void clear_bit(uint8_t* array, uint8_t num)
    {
    array[num >>3] &= ~(1 << (num & 0x7));
    }
    其中右移动三位是指,将要填入的数字除以8(毕竟我们是8位数组),我们先看看把该数字安放在哪个数组,随后我们num&0x7,这个意思是指求他的余数,即是num%0x7,我们可以计算出,该数字在数组应该右移多少位,为了程序设计方便,我们可以通过宏定义替换。
    #define SHIFT 3
    #define Mask 0x7
    void set_bit(uint8_t* array, uint8_t num)
    {
    array[num >> SHIFT] |= (1 << (num & Mask));
    }
    void clear_bit(uint8_t* array, uint8_t num)
    {
    array[num >> SHIFT] &= ~(1 << (num & Mask));
    }
    我建议做这种除法或取模运算时,尽量运用移位的方法,按位与的方法,这样计算效率会高一些。
    假设我们将数字22所在的位置值换为1,
    360af902-d5cb-4f79-a1b3-7e6e3751b23a-image.png
    首先,我们通过array[num >> SHIFT],求出我们是将array[2]中的某一位置为1,那究竟是哪一位呢?我们通过num&Mask可以得出是array[2]右移动6位置一,因此我们的置一成功。
    接下来,进入到验证部分,
    我设计了一个函数:
    bool test_bit(uint8_t* array, uint8_t num);//通过判断数字的相应位是否为1,判断该数字是否存在,返回值为布尔量
    bool test_bit(uint8_t* array, uint8_t num)
    {
    return array[num >> SHIFT] & (1 << (num & Mask));
    }
    当我们输入22时,该函数会判断array[2]的第6位是否为1,进而判断我们是否写入过该数字。下面我们演示一下运行结果:
    9a15d53c-0915-4ed4-99bb-667e5f6fcdf3-image.png
    5dc8ebc3-ea0c-4109-a8e3-0e8014589167-image.png
    假设我们改为23,
    c3d64efa-2ac7-43ac-9ca6-f1fb303a58eb-image.png
    649ef332-9490-4859-aaf8-575a5d577fc8-image.png
    输出符合预期。源代码如下:
    #define BITWORD 8
    #define SHIFT 3
    #define N 32
    #define Mask 0x7
    void set_bit(uint8_t* array, uint8_t num);
    void clear_bit(uint8_t* array, uint8_t num);
    bool test_bit(uint8_t* array, uint8_t num);
    uint8_t test_array[N / BITWORD + 1] = { 0 };

    int main()
    {
    set_bit(test_array, 22);

    printf("%d\n", test_bit(test_array, 22));
    

    }

    void set_bit(uint8_t* array, uint8_t num)
    {
    array[num >> SHIFT] |= (1 << (num & Mask));
    }

    void clear_bit(uint8_t* array, uint8_t num)
    {
    array[num >> SHIFT] &= ~(1 << (num & Mask));
    }

    bool test_bit(uint8_t* array, uint8_t num)
    {
    return array[num >> SHIFT] & (1 << (num & Mask));
    }
    我们可以通过位图法,读取文件中的数字,将位图相应位置置一,随后通过我们设计的验证函数,看看该数是否存在,如不存在,就可以输出该数据,但正如之前分析,该方法需要的内存呢非常大。
    下面我们介绍一下,该问题的解决方法,二分查找法,为了演示方便,我们假设存在一个数组,里面的数据在0-16之内,即是4位的数据。那么我们应该如何找到4位数据中的,缺失的数字呢?这里简要介绍一下思路,示意图图下
    95c83b61-1c16-48ac-99f7-43411fffd328-image.png
    假设我们有16个数,0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111,我们发现,这四位数,高位不是1,就是0,通过划分高位0和1,我们可以产生以上的树状图,比如说,第四位为1时,可以分为1000,1001,1010,1011,1100,1101,1110,1111,第四位为0时,可以分为0000,0001,0010,0011,0100,0101,0110,0111,细心观察,我们可以发现,第四位为1时,在0-15的范围内,可以分为0-7,8-15两个区间,此时,我们可以进一步细分,在8-15的区间内,第三位为1时,区间为12-15,第三位为0时,区间为8-11,在0-7区间内,第三位为1时,区间为4-7,第三位为0时,区间为0-3,依次类推,通过这种二分法,可以快速得到各个区间的数字所在区域。同时,我们可以利用原理,快速排查区间中缺少的数字,我们利用递归法,从原始数据开始进行分类,0-15中,假如第四位为1,没能在数组得到数字时,证明,8-15的区间的数字全部缺失,我们可以快速得到数组中缺失的数字,假如第四位为0没能在数组得到数字时,证明0-7的数字全部缺失,当然,有时候,缺失的数字没有那么多,高四位为1和高四位为0都能找到相应的数字,### (需要注意的是,经过上一次的分类,这时候,我们已经分别得到第四位为1和第四位为0的数字分别构成的两个数组,我们需要在此基础进一步细分查找)###,在0-7的区间内,分别查找第3位为1和第3位为0的数字,假如第三位为1的数字没有找到,证明缺失4-7的数字,假如第3位的数字没有找到,证明缺失0-3的数字,假如他们都有,我们可以将搜索到的数字,分别归为4-7和0-3两个数组,进入下一轮搜索,直到搜索到没有相应的数据,进行返回,依次类推,我们从判断第四位为1或零,一直搜索到第一位是1或0,总能把缺失的数据找出来。
    我们以0-15的数组中,缺少5和缺少11,10为例
    376751ab-e7f6-4998-8bbc-8b1e55f62dff-image.png
    当我们通过二分法,不断细分划分区间时,在{4,5}区间内通过划分第四位为0或1,我们可以找到,我们的数字5是缺失的,通过{8,9,10,11}通过划分第二位为0或1,我们可以找到,10和11是缺失的,一次找出了两个缺失数字,这就是二分法的高明之处。下面,我们演示一下代码运行的结果:
    81212c99-98f7-4d74-b012-ed44d78d1bce-image.png
    创建数组,源数组src_data有{0,1,4,2,6,9,12}7个数字,我们同时创建一个数组,src_data记录缺失的数字,并打印出来,运行结果如下:
    4048e1d2-b55a-44fd-8490-0e87bf2d6b26-image.png
    结果运行正确。下面我们贴出实现代码过程:
    #define MAX_COUNT 16
    #define Mask 0xF
    uint8_t dst_data[MAX_COUNT] = { 0 }; //目标数据(缺失的数字)
    uint8_t src_data[MAX_COUNT] = { 0,1,4,2,6,9 ,12}; //源数据
    uint8_t dst_index = 0;
    void binarysort_array(uint8_t move_bit, uint8_t* src_data, uint8_t start, uint8_t end, uint8_t count);//二分法实现函数

    int main()
    {
    binarysort_array(3, src_data, 0,16,4);
    for (int i = 0; i < dst_index; i++)
    {
    printf("%d ", dst_data[i]);
    }
    }

    void binarysort_array(uint8_t move_bit, uint8_t* src_data, uint8_t start,uint8_t end,uint8_t count)
    {
    uint8_t Bit_zero_array[MAX_COUNT] = { 0 }; //存储Bit位为0的数组
    uint8_t Bit_one_array[MAX_COUNT] = { 0 }; //存储Bit位为1的数组
    uint8_t Bit_zero_index = 0;
    uint8_t Bit_one_index = 0;

    for (int i = 0; i < count; i++)
    {
    	if (((src_data[i] >> move_bit) & 0x1) == 1)
    	{
    		Bit_one_array[Bit_one_index++] = src_data[i];   //将源数据分为两个区间,此为Bit为1的区间,并用Bit_one_index记录其数量
    	}
    	else
    	{
    		Bit_zero_array[Bit_zero_index++] = src_data[i]; //将源数据分为两个区间,此为Bit为0的区间,并用Bit_zero_index记录其数量
    	}
    }
    
    if (Bit_one_index == 0)            //假如Bit为1的数目等于0,证明区间相应的数字缺失
    {
    	for (int i = (start+end)/2; i < end; i++)
    	{
    		dst_data[dst_index++] = i;
    	}
    }
    else if (Bit_one_index != 0 && move_bit > 0)  //将Bit为0的数组送入下一轮筛选
    {
    	binarysort_array( move_bit-1, Bit_one_array, (start+end)/2,end, Bit_one_index);//不断细分区间
    	//8-15        (start+end)/2,end
    	//12-15  //4-7 
    	//14-15  //10-11 //6-7 //2-3
    	
    }
    
    if (Bit_zero_index == 0)              //假如Bit为0的数目等于0,证明区间相应的数字缺失
    {
    	for (int i = start; i < (start+end)/2; i++)
    	{
    		dst_data[dst_index++] = i;
    	}
    }
    else if (Bit_zero_index != 0 && move_bit > 0) //将Bit为1的数组送入下一轮筛选
    {
    	binarysort_array(move_bit - 1, Bit_zero_array, start,(start+end)/2, Bit_zero_index); //不断细分区间
    	//0-7     start,(start+end)/2
    	//0-4  //8-11
    	//0-1  //4-5  //8-9 //12-13  
    }
    

    }
    以上就是我关于该问题的一些个人心得,欢迎各位大佬提出建议,不吝赐教!

    1 条回复 最后回复
    1
    • SPeakS 离线
      SPeakS 离线
      SPeak d2learn-dev
      编写于 最后由 SPeak 编辑
      #2

      可以使用markdown的语法对文章进行代码高亮、分章节、加粗等

      语法

      ## 二级标题
      ### 三级标题
      > 引用块
      
      ```c
      int main() {
          return 0;
      }
      -```
      
      **注: 语法中 - 是多余的 - 加粗**
      

      对应显示

      二级标题

      三级标题

      引用块

      int main() {
          return 0;
      }
      

      注: 语法中 - 是多余的 - 加粗

      1 条回复 最后回复
      0
      • SPeakS 离线
        SPeakS 离线
        SPeak d2learn-dev
        编写于 最后由 编辑
        #3

        例如文中的代码

        #define BITWORD 8
        #define SHIFT 3
        #define N 32
        #define Mask 0x7
        
        void set_bit(uint8_t* array, uint8_t num);
        void clear_bit(uint8_t* array, uint8_t num);
        bool test_bit(uint8_t* array, uint8_t num);
        uint8_t test_array[N / BITWORD + 1] = { 0 };
        
        int main()
        {
            set_bit(test_array, 22);
        
            printf("%d\n", test_bit(test_array, 22));
        }
        
        void set_bit(uint8_t* array, uint8_t num)
        {
            array[num >> SHIFT] |= (1 << (num & Mask));
        }
        
        void clear_bit(uint8_t* array, uint8_t num)
        {
            array[num >> SHIFT] &= ~(1 << (num & Mask));
        }
        
        bool test_bit(uint8_t* array, uint8_t num)
        {
            return array[num >> SHIFT] & (1 << (num & Mask));
        }
        
        1 条回复 最后回复
        0

        • 登录

        • 没有帐号? 注册

        • 登录或注册以进行搜索。
        d2learn forums Powered by NodeBB
        • 第一个帖子
          最后一个帖子
        0
        • 版块
        • 最新
        • 标签
        • 热门
        • Online Tools
        • 用户
        • 群组