你真的了解二分查找吗(手把手教你写)
目录
😁前言
🐵二分查找法
🐶代码实现
🐨求mid的小细节
😙浅聊
😁前言
还是要回归正轨,记录一些实际、而且是我以后会回头来看的东西。这是我写博客的初衷,记录我的学习历程,在进步之路上认识一些志同道合的伙伴,一起结伴前行。如果成功的话,也能给后来者一些启发,不过这样子播放量可能没有这么高了,也没关系。诸君,加油吧!
🐵二分查找法
二分查找法的原理类似于猜数字小游戏:
在1~100的范围内猜数字n(假如是80),我第一次猜50,被提示小了;第二次猜75,提示小了;第三次猜87,提示大了;第四次猜80,猜对了。
二分查找法的执行过程就是一次一次的猜数字直到猜到我们要找的数字,返回下标。
这样的查找过程,相比于顺序查找,他带来的优势是:节省时间,时间复杂度由原来的O(n)变为O(logn)。
不过它的局限性在于:传入的数组必须是有序排列的,因为我们在查找的过程需要不断的比较大小。
🐶代码实现
现在我们传入一个数组,并要求找到数字7。
int a[10]={1,2,3,4,5,6,7,8,9,10};
为了确定范围,我们需要设置一个left,和一个right。
int left=0;int right=sizeof(a)/sizeof(a[0])-1;//sizeof(a)/sizeof(a[0])是为了确定数组有多少个数字
我们需要一个中间值mid来实现“猜数字”。
int mid=(left+right)/2;
接下来将mid与7进行比较,发现mid小于7,于是缩小范围。
if(a[mid]<7){ left=mid+1; mid=(left+right)/2;}
接下来将mid继续与7进行比较,发现mid大于7,于是缩小范围。
if(a[mid]>7){ right=mid-1; mid=(right+left)/2;}
接下来left=right=mid=6,a[mid]=7,找到了我们需要的数字。
if(a[mid]==7) return mid;//返回下标
在反复查找数字的过程中我们需要用到循环,自习观察这张图的话,会发现,循环的终止条件只有两个left>right、mid=我们要找的数(7)。
这就是以7为例子的全部过程,接下来是整合在一起的完整代码。
#includeint main(){ int a[10]={1,2,3,4,5,6,7,8,9,10}; int left=0,mid=0,i=0;//i来记录下标 int right=sizeof(a)/sizeof(a[0])-1; //sizeof(a)/sizeof(a[0])是为了确定数组有多少个元素 while(left<=right) { mid=(left+right)/2; if(a[mid]7) right=mid-1; else { printf("找到了,数字7的下标为%d",i); i=mid; } } if(left>right) printf("没找到"); return 0;}
到这里,二分查找法的基本内容就讲完了,也够用了。不过在下面我还会进行一点补充,利养成良好的变成习惯,野减少写bug的概率。
🐨求mid的小细节
二分查找法的一大优势就是时间复杂度小,O(logn),而当传入数组的元素越多则越能提现这一优势。而且我们也会在大量的数据中寻找一个数的位置。接下来讲解一个会被大多数人忽视的小细节
不论是int 类型还是long long类型,都有一个储存数字大小的上下限。比如int的就是:-2147483648~2147483647。
那么一个数既然有上限了,我们就不得不考虑一种可能,两数相加可能会超过int类型的上限,导致程序出错。
有解决的办法,而且很简单,这是两个数。并且第二个数还比第一个数大。
如果我们要求它们的中间值的话,可以将高出的那一部分分一半给矮的的那个,这样就求出了mid。代码实现如下:
mid=(right-left)/2+left;
😙浅聊
其实很多人前面那部分都知道,可能最后那里还有些含金量,哈哈,可我就是要啰嗦。毕竟主要是写给我以后自己看的,顺便给你们看看🤭🐕。写完这篇的时候肩膀还是蛮疼了,不过还是很满意,还是把想讲的讲清楚了,不管怎么说。共勉。