欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【技巧与思想】二分

程序员文章站 2024-03-17 17:49:40
...

二分

目录

二分

1.什么是二分?

2.二分的作用

3.二分的实现

4.二分的要求

5.二分的时间复杂度

6.对于上面那道题目Code

7.一般二分Code


 

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