查找算法：逐次逼近

傷城~ 2022-10-25 14:29 63阅读 0赞

最近在DIY一些电路方面东西，当模拟电路转换成数字电路时，需要用一个ADC转换器读取模拟电路输出的电压。ADC有三种实现方式，用的较多的是“逐次逼近”型的ADC。网上有很多文章介绍“逐次逼近”型的ADC的原理，但我都看得云里雾里，后来仔细一琢磨，不就是把十进制数据转化成二进制嘛，非要用一个“逐次逼近”这样看似高深的词！其实用的就是“二分法”。下面我们就来看看。  
如果东东手中有一个纸片，上面写着n = 74。根据前面说起的二分法，如果给定数据范围是1~100，则虫虫最多需要猜7次就能猜到这个数。原因是2 ^ 6 = 64 < 100 < 2^7 = 128。现在，虫虫索性把搜索范围从1 ~ 100扩大到1 ~ 128。  
猜测规则是这样：  
首先假定sum = 0  
第一次猜sum + 64，如果sum + 64 <= n，那就保留64，更新sum = sum + 64；  
第二次猜sum + 32，如果sum + 32 <= n，那就保留32，更新sum = sum + 32；  
第三次猜sum + 16，如果sum + 16 <= n，那就保留16，更新sum = sum + 16；  
第四次猜sum + 8，如果sum + 8 <= n，那就保留8，更新sum = sum + 8；  
第五次猜sum + 4，如果sum + 4 <= n，那就保留4，更新sum = sum + 4；  
第六次猜sum + 2，如果sum + 2 <= n，那就保留2，更新sum = sum + 2；  
第七次猜sum + 1，如果sum + 1 <= n，那就保留1，更新sum = sum + 1；  
第七次猜测后，猜测结束。我们发现保留的数据有64, 8, 2。则东东手上的数据n = 64 + 8 + 2 = 74。如果我们把74换成二进制表示，它就是1001010。

![在这里插入图片描述][20210201125937764.png]

所以74 = 64 \* 1 + 32 \* 0 + 16 \* 0 + 8 \* 1 + 4 \* 0 + 2 \* 1 + 1 \* 0  
= 2^6 \* 1 + 2^5 \* 0 + 2^4 \* 0 + 2^3 \* 1 + 2^2 \* 0 + 2^1 \* 1 + 2^0 \* 0  
这就是“逐次逼近”，从最大范围128的一半开始，每次减半，并用这个数据更新sum。更新幅度越来越小，直到最后得到准确的结果。用这种方式进行猜测，结果跟“二分法”是一样的，最多需要猜7次才能猜中。也就是说时间复杂度为O(logN)。下面是实现代码：

#include <stdio.h>
    #include <stdlib.h>
    
    int arr[7]; //用来存放二进制数据的数组 
    int index = 0; //当前的index 
    int sum = 0; //数组中的所有元素对应的数据之和 
    
    //猜数字，二进制法。数字范围1-128 
    void f(int n)
    {
        
    	int currentNum = 64; //128的一半 
    
    	while(currentNum > 0)
    	{
        
    		
    		if(sum + currentNum <= n)
    		{
        
    			printf("%d + %d = %d <= %d, 保留%d，写1\r\n", sum, currentNum, sum + currentNum, n, currentNum);
    			arr[index] = 1;	//确定arr[index]为1 
    			sum = sum + currentNum; //更新sum 
    		}
    		else
    		{
        
    			printf("%d + %d = %d > %d, 丢弃%d，写0\r\n", sum, currentNum, sum + currentNum, n, currentNum);
    			arr[index] = 0;//确定arr[index]为0
    		}
    		
    		index++; //下标 + 1 
    		currentNum /= 2; //currentNum减半，这就确定了这个算法的时间复杂度为O(logN) 
    	}
    }
    
    void show() //打印所有元素 
    {
        
    	for(int i = 0; i < 7; i++)
    	{
        
    		printf("%d, ",arr[i]); 
    	}
    	printf("\r\n") ;
    }
    
    int main()
    {
        
    	f(74); //计算74对应的二进制数据，数据保存在arr中 
    	show();
    	
    	return 0;
    }

运行结果如下：  
前面7个等式表示计算与判断过程。最后一行0和1表示最终转换结果。

![在这里插入图片描述][20210202142803689.png]

ADC芯片的采样原理也是类似的：ADC有基准电压 (参考电压, Vref)，一般取2.5V，所以取值范围是0~2.5V。对于八位ADC芯片，就是把2.5V分为2^8 = 256份，每一份：2.5 / 256 = 0.009766V。然后128份，64份的“逐次逼近”。如果是12位芯片，那就分成2^12 = 4096份；16位芯片就分成65536份。用这种方式，ADC芯片就可以用0和1把输入的电压值表示出来了。  
对于8位的ADC芯片，输出结果用8个引脚分别表示0和1 (高低电平) 是可以接受的，但是对于16位的ADC芯片，输出结果再用16个引脚分别表示就不太合适了。所以比较精密的ADC芯片经常采用1个引脚，在不同的时间用高低电平输出结果，这样就可以节约大量的硬件资源 (ADC芯片的引脚数和单片机的引脚数)。用单片机读取ADC芯片的结果涉及到硬件编程，这里就不再详细描述了。

[20210201125937764.png]: /images/20221024/8fc969960ba547baabb68a96f3304be3.png
[20210202142803689.png]: /images/20221024/9d34d74f25054cf39beb3f7ae84fcf76.png