顺序查找和二分查找，C语言实现

灰太狼 2023-03-01 05:43 37阅读 0赞

这一章节将讲解查找算法，包括顺序查找、二分查找。其中二分查找是通向编程高手路上的十大算法中的一种。

## 1 顺序查找 ##

虫虫和东东是兄弟俩，经常一起做游戏。这次他们玩的是猜数字。东东口袋中有10颗玻璃球，东东抓了一把 (7颗)，让虫虫猜手中有多少颗。东东只会告诉虫虫猜对了，太多了或者太少了。请问虫虫最多需要猜多少次才能猜中呢？  
我们想想可以怎么猜。  
如果从1，2，3开始按照顺序猜，那么就需要7次；  
如果是从10，9，8开始从大到小开始猜，就需要4次。  
如果随便乱猜 (随机猜)，运气最好的时候只需要1次，运气最差需要猜10次。

我们来分析一下，从小到大猜和从大到小猜其实是一回事儿：运气最好的时候只需要1次，运气最差需要猜10次。而随机乱猜的方法是不可取的，因为很难保证每次猜的数都不一样，即使能保证每次猜的数不一样，运气最差时仍然需要猜10次。既然这三种方法都一样，我们就用从小到大猜测的方式编写代码吧：

int search (int n) //猜猜东东手中有几颗玻璃球 
    {
        
    	//从1开始，从小到大猜。数组的下标从0开始哦
    	for(int i = 0; i < size; i++)  
    	{
        
    		if(arr[i] == n)
    		{
        
    			return i; //猜到了就返回下标 
    		}
    	}
    	return -1; //所有数字都不对就返回-1 
    }

这种方式称之为顺序查找。顺序查找是最简单的查找方式，适用于任何情况。运气最好的时候，时间复杂度为O(1)；运气最差的时候，时间复杂度为O(N)；平均下来这个方法的时间复杂度为O\[(1 + 2 + 3 +… + n) / n\] = O\[n \* (n + 1) / (2 \* n)\] = O\[(n + 1) / 2\] = O(N)。

## 2 二分查找 ##

我们来想一想，是不是有更好的查找方法呢？10的一半是5，如果我们第一次猜5 (太小)，那么1 ~ 5这5个数字就都排除掉了，剩下6 ~ 10这5个数字。第二次猜测8 (6与10的中间值，太大)，就可以把8 ~ 10这三个数字排除掉。接下去只剩下6和7两个数了，我们先猜6 (太小)，最后只剩下一个数字7。我们猜中了。这个方法一共猜了四次。这个方法貌似和刚才从大到小猜猜测的次数一样多嘛，这个方法有什么优势吗？  
运气最好的时候，这个方法只需要猜测1次，而运气最差的情况下，也仅仅需要猜测4次。不信？我们来看看下面的图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]  
这是一棵二叉树 (二叉树是什么东西？会结出好吃的水果吗？)。好吧，我以后再讲二叉树能不能结出水果的问题。现在只需要知道第一次猜最大值10和最小值1的平均值 (1 + 10) / 2 = 5.5，取5。第二次猜最大值10和最小值6的平均值 (6 + 10) / 2 = 8。第三次猜最大值7和最小值6的平均值 (6 + 7) / 2 = 6.5，取6。第四次猜最大值7和最小值7的平均值 (7 + 7) / 2 = 7。简单来说，就是每次猜最大值和最小值的平均值，如果猜对了，那就结束了；如果猜错了，忽略掉一半元素和刚刚猜的那个数之后，在剩余的数中继续猜。用这种猜法，5只需要猜1次就可以猜到，2和8只需猜2次，1, 3, 6, 9只需要猜3次，只有4、7和10需要猜4次。也就是说：这种方式最多也仅仅需要猜4次。可见这种方式的效率要比按顺序猜高了很多。

上述猜数字的方法就是就是位列“十大算法”之一的二分查找。它的时间复杂度为O(logN)。如果把上述猜数字的游戏扩大到1100中猜一个数字，最多只需7次，效率比按顺序猜高14倍；11000中猜一个数字，最多只需10次，效率比按顺序猜高100倍。。。这么好的查找方式，是不是看着都有点激动呢？我们来看看二分查找的代码吧。二分查找有两种实现方式，分别是递归方式和迭代方式。先来看递归方式：

//三个参数分别是：要查找的数，数组中要查找的范围。
    //low是最左边的元素的index，high是最右边的元素的index 
    int halfSearch (int n, int low, int high)
    {
        
    	if(low > high) //递归的出口1
    	{
        
    		return -1; //如果找不到要找的数，返回-1 
    	}
    	
    	//开始搜索
    	int middle = (low + high) / 2; //中间元素的下标
    	if(arr[middle] == n) //递归的出口2 
    	{
        
    		return middle; //返回的是找到的元素的下标 
    	}
    	else if(arr[middle] < n) //猜测的数比东东手中玻璃球的数量少 
    	{
        
    		//更新猜测范围：中间值、以及所有比中间值小的元素都不要了
    		low = middle + 1;  
    		return halfSearch(n, low, high); //递归搜索 
    	}
    	else //猜测的数比东东手中玻璃球的数量多 
    	{
        
    		//更新猜测范围：中间值、以及所有比中间值大的元素都不要了
    		high = middle - 1; 
    		return halfSearch(n, low, high); //递归搜索
    	}
    }

我们知道递归的时候会占用大量内存，且有可能超出最大递归次数；而用迭代方式就不会出现这样的问题。因此实际使用的都是迭代版的实现：

//三个参数分别是：要查找的数，数组中要查找的范围。
    //low是最左边的元素的index，high是最右边的元素的index 
    int halfSearch (int n, int low, int high)
    {
        
    	int middle = -1; //中间元素的下标，初始值为-1 
    	while(low <= high) //最左边的元素的下标一定比最右边的元素的下标小 
    	{
        
    		middle = (low + high) / 2; //中间元素的下标
    		if(arr[middle] == n)
    		{
        
    			return middle; //返回的是找到的元素的下标
    		}
    		else if(arr[middle] < n) //猜测的数比东东手中玻璃球的数量少
    		{
        
    			//更新猜测范围：中间值、以及所有比中间值小的元素都不要了
    			low = middle + 1;	
    		}
    		else //猜测的数比东东手中玻璃球的数量多
    		{
        
    			//更新猜测范围：中间值、以及所有比中间值大的元素都不要了
    			high = middle - 1;
    		}
    	}
    	return -1; //如果找不到要找的数，返回-1 
    }

好了，我们看一下上面的代码是不是有问题：  
数学的角度看，middle = (low + high) / 2这行代码没有问题。但是从编程语言的角度看，low + high有可能超出C语言中int值的范围，所以需要在不改变意思的情况下修改代码。那么怎么改进呢，下面是三种改进方式，从数学的角度看，这三种方式是一样的。但是从编程语言的角度看，这三种方式是不一样的。我们分别进行讨论：  
1、middle = low / 2 + high / 2  
2、middle = low + (high - low) / 2  
3、middle = high + (low - high) / 2  
如果low和high都是奇数，例如1和5，middle应该等于3。第一种改进方式，middle = 1 / 2 + 5 / 2 = 0 + 2 = 2，得到错误的结果。  
第二种方式：无论哪种情况，都能得到正确的结果。可以采用这种改进方式。  
第三种方式：看上去跟第二种方式很相似。当low = 2，high = 5时，middle应该等于3，但是middle = 5 + (2 - 5) / 2= 5+ (-3) / 2 = 5 + (-1) = 4。得到错误的结果。

综上所述，需要把middle = (low + high) / 2改成：middle = low + (high - low) / 2。

下面是二分查找的最终代码：

//三个参数分别是：要查找的数，数组中要查找的范围。
    //low是最左边的元素的index，high是最右边的元素的index 
    int halfSearch (int n, int low, int high)
    {
        
    	int middle = -1; //中间元素的下标，初始值为-1 
    	while(low <= high) //最左边的元素的下标一定比最右边的元素的下标小 
    	{
        
    		//middle = (low + high) / 2; 这种方式可能会导致数据超出int的范围
    		middle = low + (high - low) / 2 //计算中间元素的下标
    		if(arr[middle] == n)
    		{
        
    			return middle; //返回的是找到的元素的下标
    		}
    		else if(arr[middle] < n) //猜测的数比东东手中玻璃球的数量少
    		{
        
    			//更新猜测范围：中间值、以及所有比中间值小的元素都不要了
    			low = middle + 1;	
    		}
    		else //猜测的数比东东手中玻璃球的数量多
    		{
        
    			//更新猜测范围：中间值、以及所有比中间值大的元素都不要了
    			high = middle - 1;
    		}
    	}
    	return -1; //如果找不到要找的数，返回-1 
    }

上面说了二分查找的那么大的优势，这里不能不提醒一下，二分查找对被查找的数组是有要求的：所有元素必须是有序的。如果数组中的元素的次序是乱的，那就没法用二分查找了，只能用顺序查找。如果这个数组只查找一次，那就用顺序查找吧，时间复杂度为O(N)。如果这个数组会被查询多次，那么我就建议先对数组中的元素进行排序，然后再用二分查找。排序算法的时间复杂度为O(N \* log N)。虽然前面花了很多时间，但是正所谓“磨刀不误砍柴工”，后面的查找就要比顺序查找快多了，多次查找之后，总的效率会提高不少。

二分查找中最重要的思想就是“二分”，也就是：middle = low + (high - low) / 2。如果把这个公式换成：middle = low + (key - a\[low\]) \* (high - low) / (a\[high\] - a \[low\])，二分查找就变成了插值查找。插值查找对于分布比较均匀的数组查找效率比较高，但对于分布极端不均匀的数组，效率反而降低。最关键的是，当a\[high\] - a \[low\] = 0时，分母变成0，所以插值查找算法是有缺陷的，确切的说，它是有限制条件的。而二分查找没有这些问题，且效率十分稳定，因此二分查找是最常用的查找算法。

最后，我想说一下，“二分查找”这个名字取的名不符实。该算法在获取数组的中间值之后，实际上是把数组分成三部分，而不是两部分。以下面1 ~ 8这8个数字为例，数组被分为：左边部分 (1 ~ 3)、中间的值 (4)、右边部分 (5 ~ 8)。类似的情况在快速排序中也会出现。不过这仅仅是名字上的问题，不影响我们对算法本身的理解。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]

思考一个问题：如果要在一个从小到大有序的数组arr中找第k大的数，则arr\[k - 1\]就是要的那个数。但是如果数组arr中的数据不是有序的，我们该怎么办呢？  
我先提出三种思路：  
1、参考选择排序：从n个数中顺序查找，找到最大值，然后把这个最大值去掉。然后继续在剩下n - 1个数中顺序查找，找到最大值。这样重复k次，就可以得到第k大的元素了。这样做的时间复杂度为O(N \* K)。  
2、对这n个数从大到小排序，然后第k - 1个数就是第k大的值。排序的时间复杂度为O(N \* logN)，求第n - 1个数的时间复杂度为O(1)，所以总的时间复杂度为O(N \* logN)。如果使用桶排序，时间复杂度可以降低到O(N)，但是桶排序存在一些问题，这里暂且不讨论。这个实现方法需要排序算法，请查阅排序章节后再实现这个功能。  
3、进行部分排序：借助于堆排序，建立一个有k个数组成的小顶堆。然后遍历剩余元素，跳过比堆顶元素小的数，如果被遍历的元素比堆顶元素大，就用这个数取代堆顶元素，并重新维护这个堆。这样做的时间复杂度为O((N- k) \* logK)，如果k远小于n，则时间复杂度 = O(N \* logK)。这个代码在扩展篇中已经实现了，请前往扩展篇中查阅。

聪明的读者，你还能想到更快的方法吗？“线性查找”算法可以把top k问题的时间复杂度降低到O(N)。请区分一下，这里所说的是“线性查找”，而不是上面已经介绍过的“顺序查找”。  
由于线性查找算法需要用到插入排序算法和快速排序的划分思想，我们就把它放在扩展篇中介绍。

## 3 扩展 ##

在数组中使用二分查找确实可以非常高效的找到数据，但是如果被查找的数据是不固定的 (可能会动态的增加、删除数据)，这时如果还是用数组进行储存数据就显得不太合适了。因为在数组中增加、删除数据的时间复杂度为O(N)。添加数据之后再进行查找，时间复杂度为O(N + logN)，效率就变得很低。针对这种情况，科学家们设计了二叉查找树。二叉查找树的内容我们将在“树”这个章节中进行介绍。

最后，我们再介绍一种散列表查找，我们暂时称之为“地图”吧，请跟数据结构中的“图”区分开。例如，打仗时，指挥官不会自己跑到要被轰炸的地方，高喊着“向我开炮”，而是会在指挥部，用手指着地图上的某一个点，让士兵发射炮弹到这个位置。士兵们就可以对这个点进行精确打击。为什么这样是可行的呢？原因是地图上的某一个点与地球上某一个位置是一一对应的。只要知道地图上某一个点的位置，就可以算出地球上对应位置的坐标。这种数据结构可以把两个看似毫不相关的数据关联在一起。地图上的一个点称之为key，地球上某一个实际位置称之为value。key <–> value这两个数据往往是一起使用的，称之为“键值对”。这种数据结构用的比较多，有趣的是它在不同的语言中有不同的叫法，例如Java中称之为HashMap、HashTable；C\#中叫Dictionary；Python中则称之为字典。恰当地使用这种数据结构可以极大地提高编程效率，降低代码复杂度。这里就不详细介绍这个算法的实现方式了。

关于查找算法就到这里吧。其它的查找算法，例如Fibonacci查找、字典树、多路查找树等查找算法用的相对较少，请有兴趣的朋友查看参考书吧。

## 4 思考 ##

如果有1000个人同时在10亿个数据中进行查找，怎样才能保证每个人都能在很短时间里得到自己想要的结果？

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/783660f759c144b6a9f3b37c0f89da43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]: /images/20230209/869c19aae1c446b5948641da0c435425.png