【技巧与思想】二分
二分
目录
1.什么是二分?
二分,是二分查找的简称,又叫折半查找,是一种用于快速查找的工具,也可以说是一种技巧与思想。
2.二分的作用
也许你以前玩过一个游戏,就是一个人在心中想一个数,规定这个数大于0并且小于100,然后让你猜他想的那个数,你每猜一次他都会告诉你你猜的数是大了还是小了,最后直到你根据他的提示不断缩小他想数的范围并找到他想的数,其实二分就是用来快速找到“他心里所想的那个数”。如果用二分查找来找“他心里所想的那个数”的话,你最多只用猜7次。
3.二分的实现
首先,我们必须要规定一个边界,即“那个数的上限和下限”,这样我们才能进行查找,设这个数的下限为l,上限为r。如果我们想要尽可能猜的次数少的话,那么我们是不是每次得猜尽量是上限和下限最中间的数?没错,我们每次取一个l和r的中间数,mid=(l+r)/2,(上限+下限)/2就是上限和下限的中间数了,这里不讲原因。接下来我们要判断这个mid是大于他想的数还是小于他想的数,如果大于他想的数,那么他想的数的范围就可以锁定在l~mid-1中,反之,就是在mid+1~r中。那么此时上限和下限就要更改,即r=mid-1或l=mid+1,然后再重复此过程直到mid等于他想的数就可以退出了。
但是假设只给你几个数呢?其实也是一样的。我们来模拟一下,假设给你{1,22,54,78,100}这几个数,我随机想一个数,假设是22,那么首先你的上限是5,下限是1(表示有几个数),然后你再进行二分,取一个中间的数mid=(l+r)/2=3(这里表示的是第3个数,即在第1个数到第5个数之间,第3个数是最中间的数),然后我们看第3个数,第三个数大于了22,所以要将上限改为3-1,即r=mid-1=2。那么我们再在第1个数和第2个数中找一个中间数,mid=(l+r)/2=1。第1个数小于了22,所以我们要将下限改为1+1=2,即l=mid+1=2。最后我们再找2和2的中间数,于是mid=(l+r)/2=2。第二个数刚好就是我想的那个数了。
4.二分的要求
什么?二分还有什么要求,不就是要给定上限和下限吗?如果你这样想的话,那就大错特错了。
1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。这是什么意思呢?那刚才的例子来说,其实1~100这些数都早已按从小到大的顺序排列好了,所以你才可以使用二分查找。假设我将这100个数全部打乱,那你就不能用二分了。举个简单的例子,在{100,1,54,78,22}这5个数中,我想的数还是22,那么你如何用二分查找呢?首先你的上限是5,下限是1(表示有几个数),然后你再进行二分,取一个中间的数mid=(l+r)/2=3(这里表示的是第3个数,即在第1个数到第5个数之间,第3个数是最中间的数,即54)发现54大于了22,那么你就要调整上限,r=mid-1=2。再取中间数mid=(l+r)/2=1。第一个数(100)大于22,再调整上限,r=mid-1=0。这个时候r<l,也就是说上限都小于下限了,那么就退出,但是你始终没有找到我想的那个数。所以这就证明了二分只能用在一串有序的数中。那么对于这道题目而言,难道就真的没有办法用二分找到我想的那个数了吗?非也,既然是无序的,那你就给它排个序不就成有序的了吗?至于排序用什么都行(选择、冒泡、快速排序、归并排序、堆排序......)
5.二分的时间复杂度
二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
时间复杂度无非就是while循环的次数!
总共有n个元素,
渐渐跟下去就是n,n/2,n/4,....n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,(是以2为底,n的对数)
所以时间复杂度可以表示O(h)=O(log2n)
6.对于上面那道题目Code
给你n个互不相等的数,以及一个在这n个数中的一个数,问你这个数是这n个数中第几大的数。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
int n,k,a[1000000];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&k);
sort(a+1,a+n+1);
int l=1,r=n,mid,ans;
while(l<=r){
mid=(l+r)/2;
if(a[mid]>=k){
r=mid-1;
ans=mid;
}
else l=mid+1;
}
printf("%d\n",n-ans+1);
return 0;
}
7.一般二分Code
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
int l=1,r=100000000,mid;
while(l<=r){
mid=(l+r)/2;
if(check(mid)){
l=mid+1;
}
else{
r=mid-1;
}
}
return 0;
}
作者:zsjzliziyang
QQ:1634151125
转载及修改请注明
本文地址:https://blog.csdn.net/zsjzliziyang/article/details/82023941
上一篇: jdbc 获取连接步骤
推荐阅读
-
【技巧与思想】二分
-
LOJ#6387 「THUPC2018」绿绿与串串 / String (Manacher || hash+二分)
-
整形有序数组查找--遍历法与折半法/二分法
-
数据结构与算法(8)——二分查找
-
在一个有序(增序)数组中查找具体的某个数字n 与二分法查找算法
-
C++类与对象一:OOP思想、类和对象、this指针
-
面向对象的思想(类与对象及其应用)、成员变量和局部变量、匿名对象、 封装(private) 、this关键字
-
Flex3与AS3.0 API,技巧与工具网站的收集 博客分类: 网络精华(转) flexasAPIflex工具flexAPI
-
浅析Java中局部变量与成员变量同名解决技巧
-
浅析Java中局部变量与成员变量同名解决技巧