二分查找知识点及练习题

这篇具有很好参考价值的文章主要介绍了二分查找知识点及练习题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

知识点讲解

一、没有相同元素查找

请在一个有序递增数组中(不存在相同元素),采用二分查找,找出值x的位置,如果x在数组中不存在,请输出-1!

 输入格式

 第一行,一个整数n,代表数组元素个数(n <= 600000)

第二行,n个数,代表数组的n个递增元素(1<=数组元素值<=2000000)

 第三行,一个整数x,代表要查找的数(0<=x<=2000000)

输出格式

按题意输出位置或者-1。

输入/输出例子1

输入:

10

1 3 5 7 9 11 13 15 17 19

3

输出:

2

【分析】:当我们要从一个序列中查找一个元素的时候,最快想到的方法就是顺序查找法(即:从前到后依次查找)。但这种方法过于无脑,就是暴力的把每个元素都排查一遍。元素个数少的时候还行,一旦元素个数多起来,效率非常低下。

分查找法也称折半查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log2n)完成查找任务。

它的基本思想是,先把n个元素从小到大排序,然后取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果x<a[n/2],则我们只要在数组a的左半部分继续搜索x。如果x>a[n/2],则我们只要在数组a的右半部分继续搜索x,直到查找成功或查找完毕为止。

以下是二分查找的查找过程图示:

二分查找知识点及练习题,算法,二分查找,c++

二分查找知识点及练习题,算法,二分查找,c++

二分查找的算法框架一如下:

left=1;right=n;

while(left<=right)

{

   mid=(left+right) / 2;

   if (x==a[mid]){ printf("%d",mid)}//查找成功,输出mid的值并结束;

   if (x>a[mid]) left=mid+1;//往数组的右边找

   if (x<a[mid]) right=mid-1;//往数组的左边找

}
printf("查找不成功")//输出“查找不成功”

在查找过程中我们每次把查找的范围缩小了一半,在最坏情况下查找log2n次就可以得到结果。

注意:

1.二分查找是在数据有序的情况下才能完成,即进行二分查找前数据必须先排序。上述框架是以数据已从小到大排序为前提条件的。

2.这里可能解的范围为[left,rigth],当x>a[mid]时,x如果存在的话应该是在数组的[mid+1,right]中,此时的left改为mid+1,而不是mid;同理,当x<a[mid]时,x如果存在的话应该在数组的[left,mid-1]里,此时的right应该改为mid-1,而不是mid。

二分查找知识点及练习题,算法,二分查找,c++

二分查找知识点及练习题,算法,二分查找,c++

二分查找知识点及练习题,算法,二分查找,c++

二分查找的算法框架二如下:

left=0;right=n+1;

while(left+1<right)

{

 mid=(left+right) / 2;

 if (x==a[mid]){ printf("%d",mid);}//查找成功,输出mid的值并结束;

 if (x>a[mid]) left=mid;//往数组的右边找

 if (x<a[mid]) right=mid;//往数组的左边找

}

printf("查找不成功");//输出“查找不成功”

二、有相同元素的查找

1、求左侧边界:

这样就引申出一个问题:如何二分查找求左侧边界。当查找的数字v存在时,得到它出现的第一个位置,假如不存在,就得到比它大的第一个数的位置。

这样只要把二分查找修改一下:

为了查找方便,我们在数组a[0]处插入一个最小的数-1,在a[n+1]处插入一个无穷大数,left指向0,right指向n+1,这样解空间为(left,right]。

1、 情况a[mid]>=v时:right=mid(至少已经找到一个,或者mid可能已经是比v大的数中最小的一个,或者左边可能还有比v大的,因此区间变成(left,mid]。)

2、 情况a[mid]<v时;left=mid,也就是解只可能在右边。

例如:

-1 2 3 5 6 7 7 8  10000000 中查找v=7

第一轮:left=0,right=9,解空间为(0,9]那么mid=(0+9)/2=4,因为a[4]=6<7,那么left=mid=4,解空间应该是(4,9]。

第二轮left=4,right=9, mid=(4+9)/2=6 ,因为a[6]=7==7,那么right=6,也就是解空间为(4,6]。

第三轮 left=4,right=6, mid=(4+6)/2=5 ,因为a[5]=7==7,那么right=5,也就是解空间为(4,5]。

因为解空间只有一个解,所以解为下标5,所以left+1==right为程序结束条件。

【求下界核心程序如下】:

a[n+1]=1000000000;

a[0]=-1;

int findleft(int left,int right,int value)//调用时left=0,right=n+1

{

while(left+1<right)  //如果解区间不止一个,那么继续二分

{

   int mid=(left+right)/2;  //取中间值

   if(a[mid]>=value)//如果找到一个等于或者大于value的数,解空间为(left,mid]

  right=mid;

else

   left=mid; //如果找到一个小于value的数,解空间为(mid,right]

}

return right;

}

2、求右侧边界

如何二分查找求右侧边界。当查找的数字v存在时,得到比它大的第一个数的位置。

方法如下:

为了查找方便,我们在数组a[0]处插入一个最小的数-1,在a[n+1]处插入一个无穷大数,left指向0,right指向n+1,这样解空间为(left,right]。

1、 情况a[mid]>v时:right=mid(至少已经找到一个,或者mid可能已经是比v大的数中最小的一个,或者而左边可能还有比v大的,因此区间变成(left,mid]。)

2、 情况a[mid]<=v时;left=mid,也就是解只可能在右边。

【求上界核心程序如下】:

a[n+1]=1000000000;

a[0]=-1;

int findright(int left,int right,int value)//调用时left=0,right=n+1

{

while(left+1<right) //如果解区间不止一个,那么继续二分查找

{

   int mid=(left+right)/2;

   if(a[mid]<=value)//找到一个小于或者等于value的数,解空间为(mid,right)

  left=mid;

else

  right=mid; //如果找到一个大于value的数,解空间为(left,mid)

}

return right;

}

拓展:另外一种二分查找形式找左侧和右侧:

根据c++的整除是求下界,那么两个相邻的数求平均数等于较小的数,也就是当求区间解时,当左区间不能满足要求时,可以让left=mid+1,跳出条件变为L<R,也就是解空间为(L,R]。

找左侧核心程序如下:

int L=0,R=n+1,mid;

while(L<R)

{

   mid=(L+R)/2;

   if(a[mid]<x)

       L=mid+1;

   else

      R=mid;

}

if(a[R]==x) printf("%d ",R);

else printf("-1 ");

找右侧核心程序如下:

int L=1,R=n+1,mid;

while(L<R)

{

    mid=(L+R)/2;

     if(a[mid]<= x)

        L=mid+1;

    else

        R=mid;

   

}

if(a[L-1]==x) printf("%d ",L-1);

else printf("-1 ");

讲完知识点,我们来看看几道习题

习题部分

进击的河流

有一个铁人三项运动员,他的弱点是就是游泳,正好他家旁边有n条流速不同的河流,他想锻炼m天。
在这m天中,他每天都有不同的体力,他只能在流速小于他体力的河流里游,不然他就会被冲到太平洋(?!!!!!!)。
他想知道每天他能在多少条河里游泳。

输入格式

第一行:n(n<=10^6)

第二行:n个数,分别表示n条河流的流速

第三行:m(m<=10^6)

接下来有m行,分别表示m天中运动员不同的体力

输出格式

m行,分别表示运动员m天里每天他能在多少条河里游泳

输入/输出例子

输入:

10
1 1 1 2 2 2 2 3 4 4
5
3
2
5
4
1

输出:

7
3
10
8
0

代码:

#include<bits/stdc++.h>
using namespace std;
int n,k,a[10000005],x;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    cin>>k;
    while(k--){
        scanf("%d",&x);
        int l=0,r=n+1,m=0;
        while(l+1<r)
        {
            m=(l+r)/2;
            if(a[m]<x)l=m;
            else r=m;
        }
        cout<<r-1<<"\n";
    }
    
    return 0;
}

 生死狙击

小飞最近迷上了一个叫生死狙击的游戏。不过他的技术并不好,假设他的战斗力是•x。不过,他的战斗力是由心情来定的,每天都不同。现有一群(1<=n<=100000)也是玩生死狙击的朋友,他们也有战斗力。小飞想找一些比自己强的人玩,提高自己的战斗力,如:小烨,小祖,小明等。
小飞一共玩了m天,假设其他人的战斗力不变。问:小飞每天可以找到多少比自己强的人。

输入格式

第一行输入一个n,表示有n个朋友;(1<=n<=100000)
第二行输入n个朋友的战斗力;每个朋友战斗力不超过longint;(已有序);
第三行输入一个m,表示有m天;(1<=m<=100000)
接下来m行,表示小飞每天的战斗力;小飞战斗力不超过longint;

输出格式

共m行,每一行小飞每天找到的人数;

输入/输出例子

输入:

5
1 1 3 5 5
3
0
2
5

输出:

5
3
0
代码:
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[10000005],x;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    cin>>k;
    while(k--){
        scanf("%lld",&x);
        long long l=0,r=n+1;
        while(l+1<r){
            long long m=(l+r)/2;
            if(x>=a[m])l=m;
            else r=m;
        }
        printf("%lld\n",n-r+1);
    }
    return 0;
}

选人

在一条坐标轴上,有N头奶牛,第i头奶牛的位置是Xi。FJ现在要选出三头奶牛去比赛,不妨假设选择了奶牛a,b,c。那么必须要满足:

1、Xa < Xb < Xc。

2、 Xb-Xa <= Xc - Xb <= 2 * (Xb - Xa)。

你的任务是计算,FJ总共有多少种不同的选择?

输入格式

第一行,一个整数N。 3 <= N <= 1000。 接下来有N行,第i行是整数Xi。

输出格式

一个整数。

输入/输出例子

输入:

5 
3 
1 
10 
7 
4

输出:

4

样例解释

可以有4种不同的选择,每种选择对应的3头奶牛的坐标是: {1,3,7} {1,4,7} {4,7,10} {1,4,10}

代码:
#include<bits/stdc++.h>
using namespace std;
long long n,s,q[10000000],t,m,ans,ans2,l,r;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&q[i]);
    sort(q+1,q+1+n);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int l=0,r=n+1,m;
            while(l+1<r)
            {
                m=(l+r)/2;
                if(q[j]-q[i]>q[m]-q[j])l=m;
                else r=m;
            }
            ans=l;
            l=0,r=n+1;
            while(l+1<r)
            {
                m=(l+r)/2;
                if(q[m]-q[j]>2*(q[j]-q[i]))r=m;
                else l=m;
            }
            ans2=l;
            t+=ans2-ans;
        }
    }
    cout<<t;
    return 0;
}

能不能留下关注和点赞........

安慰一下啥也不会的小学生..........文章来源地址https://www.toymoban.com/news/detail-857271.html

到了这里,关于二分查找知识点及练习题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据库系统概述——第六章 关系数据理论(知识点复习+练习题)

    🌟 博主: 命运之光 🦄 专栏: 离散数学考前复习(知识点+题) 🍓 专栏: 概率论期末速成(一套卷) 🐳 专栏: 数字电路考前复习 🦚 专栏: 数据库系统概述 ☀️ 博主的其他文章: 点击进入博主的主页​​​​​ 前言: 身为大学生考前复习一定十分痛苦,你有没有过

    2024年02月09日
    浏览(52)
  • C++ Primer 6.3 返回类型和return语句 知识点+练习题

    用在返回值类型为void的函数中,可以不写return,因为此类函数会在最后一句隐式执行return; 可以自己写return;在函数里类似于break,直接退出 除return;还可以return func();此时func为返回值为void的函数 先拷贝再传值 不要返回局部对象的引用或指针 :函数完成后,它所占用的

    2024年01月17日
    浏览(70)
  • C++ Primer 6.5 特殊用途语言特性 6.6 函数匹配 知识点+练习题

    在给定的作用域中一个形参只能被赋予一次默认实参 局部变量不能作为默认实参,函数结束就销毁,无法当作默认实参。 除此之外,只要表达式的类型可转换成形参所需要的类型,则可以作为默认实参 将函数定义为内联函数,即加上inline,在编译时内联展开代替函数 在编译

    2024年01月22日
    浏览(46)
  • 数据库系统概述——第三章 关系数据库标准语言SQL(知识点复习+练习题)

    🌟 博主: 命运之光 🦄 专栏: 离散数学考前复习(知识点+题) 🍓 专栏: 概率论期末速成(一套卷) 🐳 专栏: 数字电路考前复习 🦚 专栏: 数据库系统概述 ☀️ 博主的其他文章: 点击进入博主的主页​​​​​ 前言: 身为大学生考前复习一定十分痛苦,你有没有过

    2024年02月10日
    浏览(69)
  • C++ 类与对象中类的深入知识点+完整思维导图+基本练习题+深入细节+通俗易懂建议收藏

    本章我们接着对类和对象进行探索,这是一个在我们c++中比较重要的知识点,下面我们才是我们类和对象的更加深入且困难的知识点,希望你能通过这篇文章对类其有更加深入的了解。 话不多说安全带系好,发车啦(建议电脑观看)。 附:红色,部分为重点部分;蓝颜色为

    2024年02月04日
    浏览(64)
  • C++ 命名空间、域、缺省参数、函数重载、引用、auto、内联函数的知识点+完整思维导图+基本练习题+深入细节+通俗易懂建议收藏

            从本章开始我们正式进入到C++的内容,对此如果没有学习过C语言的建议先将C语言系统的学习一遍后再来(已经更新完在专栏就能看到)。 话不多说安全带系好,发车啦 (建议电脑观看) 。 附:红色,部分为重点部分;蓝颜色为需要记忆的部分(不是死记硬背哈,

    2023年04月24日
    浏览(106)
  • 86. print输出函数知识拓展(有练习题)

    print[prɪnt]:打印,输出。 【功能】 输出程序结果,默认输出到屏幕即程序终端,也可以输出到文件中。 【语法参考】 【参数说明】 value 要输出的值,可以是字符串、整数、浮点数等各种类型的变量等等。 ... 值列表:表示可以一次性打印多个值,值与值之间用英文逗号

    2024年02月05日
    浏览(47)
  • 北京理工大学操作系统复习——习题+知识点

    由于操作系统知识太多,再加上我总结的比较细,所以一篇放不下,拆分成了多篇文章。 操作系统笔记——概述、进程、并发控制 操作系统笔记——储存器管理、文件系统、设备管理 操作系统笔记——Linux系统实例分析、Windows系统实例分析 北理工操作系统实验合集 | API解读

    2024年02月03日
    浏览(61)
  • 系统分析师每日练习错题知识点

    计算机网络: RIP协议存在的一个问题就是当网络出现故障的时候,要经过比较长的时间才能把信息传送到所有的路由器。在这个中间过程中,实际就是路由环路的问题;当发生路由环路的时候,路由表会频繁的进行变化,从而导致路由表中的一条或者几条,都无法收敛,结果

    2024年02月09日
    浏览(66)
  • 数据结构选择题练习知识点整理【3】

    n 个点连通且无环的简单无向图为连通图,连通则至少有n-1条边,无环则只有n-1条边。n个点连通且无环的简单无向图有n-1条边,非零个数为2(n-1),零元素个数为n^2-2(n-1)。得出零元素个数为n²-2n+2。 算术表达式 中缀、前缀、后缀的互相转换 中-前 从右到左 数字入栈,碰见运算

    2024年02月06日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包