彻底轻松搞定顺序存储结构元素的二分查找的时间复杂度优势以及如何算时间复杂度

客官°小女子只卖身不卖艺 2022-06-05 03:25 193阅读 0赞

二分查找也叫折半查找，根据字面意思大概知道是怎么个查找具体一个元素的吧。

首先分析下查询过程：  
我们先通过被查询的数组得到该被查询数组的第一个索引和最后一个索引值，假如我们拿数组10个元素来做例子

我们得到索引0和索引9 mid = (min(0) + max(9))/2 mid =5 得到中间索引然后就测试当前这个索引对应的元素是不是我们想要的元素，是的话就直接返回元素的索引下标，

否则我们根据和当前元素的大小，确实我们被查询元素在什么区间。  
现在引出了为什么二分查找的对象必须是有序的，  
既然规定是有序的，假如我们查询的元素大于当前的中间值，我们默认数据是从小到大，  
那么我们的查询对应肯定是在索引值为6和9之间，你们说是不是。因此我们把查询范围直接锁定在6和9之间，还是用同样的办法继续将循环范围减半。 最好只有一个元素的时候比较之后就不用在折半数组了，直接退出循环。

贴上算法：
    //折半算法实现代码  c++版本 其实语言没有关系
    //用户想用我这个算法查询一个元素在数组array中的索引位置
    //直接告诉我们数组的起点索引和终点索引 以及查询的对于key
    void BinSearch(int array[] ,int low, int high,int key)
    {
    
        //既然用了递归，那么什么时候退出呢
        //当我们的数据只有一个了我们直接比较就可以 比较后发现不等就直接退出了反正找不到了
        if(low >= high)
        {
            return -1;    //-1表示没有找到
        }
    
             //开始为比较元素大小准备中间变量  得到被查询数组的中间元素索引值
             int  mid = (low + high)/2;   
    
        //开始比较元素是不是想要的
        if(array[mid] == key)//找到了
        {
            return mid;   //直接把查询到的key值返回给用![这里写图片描述](https://img-blog.csdn.net/20171116132618667?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMzMwNjA0MDU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)户
        }
        else if(arrat[mid] > key)  //发现查询对象是在我们的数组中间索引的左边
        {
              //缩小了查询的范围，还是相同问题，因此可以用递归算法查询
              //我需要把被查询数组和数组的下标以及被查询的数据传给当前函数
              return BinSearch(array,low, mid-1, key);
        }else   //说明查询对象在mid的右边 那么把对应需要的索引范维传过去
        {
              return BinSearch(array,mid + 1, high, key);
        }
    }

下面进入我们的主题：

先看图  
![这里写图片描述][SouthEast]

图理可不是二叉树哦。我们拿来用，我们的数据还是用顺序表存储，总共11个元素，  
并且存储次顺依次是 2 3 10 15 20 25 28 29 30 35 40，大家发现没有我们用中序遍历这个二叉树图就是这个序列。

好了 我们的数组是存的上序序列，假如我查找40这个数， 进入我们的算法查找过程我们先是和mid = 5 就是25比较大小，比较一次。

然后没有找到的话就假如当前的查询数据大于25，那么我们就转到30根节点那边的树，和30比较又 是1次，  
接着转35那棵树和35比较是1次，然后就是40又是一次找到了。 总共是4次比较，

大家细细数数二叉树的高度也是4啊，那么查询次数是不是就是所要的元素在二叉树的高度呢。  
回答是对的， 比如我们想找30的话，我们只要比较2次就可以。那么我们的平均查询次数是怎么算呢。  
答案是把每个元素查询的次是求和处以全部节点数： ASL = (1 + 2\*2+ 3\*4 + 4\*4)/11;  
那么ASL 什么呢 是平均查询长度 为啥 看这里：Average Search Length 好了吧，哈哈

那么1 2 3 4 又是什么呢，1表示我们查询25这个元素需要一次 ，2 是2次刚好有10和30个元素所以就是4次。 其他一样。如果是n个元素，那么这个平均查询次数就是关于n的函数，就可以算法时间复杂度了

我们知道二叉树的高度和节点在数学上的关系，假如有n个节点，树的高度为h，那么h = log2^(n + 1);

具体是为什么我们可以代数测试。为了简单起见，当树的高度为1， 那么节点n+ 1 = 2 ，从而n = 1.满足二叉树  
当树高度为2 ， n + 1 = 4 即 n = 3,

当我们的数组元素是n个的时候，我们在来求二分法找元素的ASL的大小，不好写就直接上图了

![这里写图片描述][SouthEast 1]

具体算时间复杂度的公式直接给出把。就是0（log2^n） 他就是数学里面的一个曲线图，根据这个图我们知道查询效率根据这个n的变化的趋势; 这个根据平均长度很多容易得出，为什么去掉 + 1 和- 1，我估计说下，我那线性表按照次顺查找来说，简单点，假如平均查找次数是2n + 1， 那么时间复杂度是0(n),  
为什么，我们需要把这个2n + 1直线画出来，我们可以看到n变化带来y的变化趋势， 因此其实时间复杂度是看图的走势，也就是说随着数据n的无限增大，需要的查询次数是不是增加很快。如果说变得非常快你的算法需要改进了，如果变得很小，甚至就是个常量，那么恭喜你牛B的算法出了，不用优化了，至少目前很多年是不会。0(n) 和0(log2^n)的走势图 肯定后面直线的一定会在上面也就是说次数会一直高，越到后面拉的差距也越大。

大家发现了吗，同样都是数组来存数据，我们在数组中找个元素，我们用循环依次比较法和二分法区别就很大了。特别在海量数据中查询更加明显。商业项目中的数据你觉得那几个吗，肯定是千万级别。

所以你知道算法为啥在公司必考么。 写出那么弱的算法的很多算法在项目中根本不能用的，用户体验是接受不了。所以跟着我把数据结构和算法彻底搞定在进军其他的技术把。

曲线图就不贴了 大家有精力可以看看数学视频或者自己画出来。

其实计算时间复杂度其他的就类似了，知道了方法靠的是什么就是死啃了 ，没有捷径， 这个时候对于觉得数学到底对游戏开发有什么好处啊，要不要学啊。就很明显了，画图 log等函数这些其实都是数学中的知识，高中学过吧，不记得的话可以复习下哦。遇到不懂得一一搞定，后面不懂得越来越来少，一直在托不懂得还是不懂。、

[SouthEast]: /images/20220605/1ebb55489db94d8cbcc690b6c9de8276.png
[SouthEast 1]: /images/20220605/34e2f7a84e13493ebd02c3cb1fed3f5d.png