知識點(diǎn)講解

一、沒有相同元素查找

請?jiān)谝粋€(gè)有序遞增數(shù)組中（不存在相同元素），采用二分查找，找出值x的位置，如果x在數(shù)組中不存在，請輸出-1！

?輸入格式

?第一行，一個(gè)整數(shù)n，代表數(shù)組元素個(gè)數(shù)（n <= 600000）

第二行，n個(gè)數(shù)，代表數(shù)組的n個(gè)遞增元素（1<=數(shù)組元素值<=2000000）

?第三行，一個(gè)整數(shù)x，代表要查找的數(shù)（0<=x<=2000000）

輸出格式

按題意輸出位置或者-1。

輸入/輸出例子1

輸入：

10

1 3 5 7 9 11 13 15 17 19

3

輸出：

2

【分析】：當(dāng)我們要從一個(gè)序列中查找一個(gè)元素的時(shí)候，最快想到的方法就是順序查找法（即：從前到后依次查找）。但這種方法過于無腦，就是暴力的把每個(gè)元素都排查一遍。元素個(gè)數(shù)少的時(shí)候還行，一旦元素個(gè)數(shù)多起來，效率非常低下。

分查找法也稱折半查找法，它充分利用了元素間的次序關(guān)系，采用分治策略，可在最壞的情況下用O(log2n)完成查找任務(wù)。

它的基本思想是，先把n個(gè)元素從小到大排序，然后取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止。如果x＜a[n/2]，則我們只要在數(shù)組a的左半部分繼續(xù)搜索x。如果x＞a[n/2]，則我們只要在數(shù)組a的右半部分繼續(xù)搜索x，直到查找成功或查找完畢為止。

以下是二分查找的查找過程圖示：

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

left=1;right=n;

while(left<=right)

{

? ?mid=(left+right)?/?2;

? ?if (x==a[mid]){ printf("%d",mid)}//查找成功，輸出mid的值并結(jié)束;

? ?if?(x>a[mid])?left=mid+1;//往數(shù)組的右邊找

? ?if?(x<a[mid])?right=mid-1;//往數(shù)組的左邊找

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

在查找過程中我們每次把查找的范圍縮小了一半，在最壞情況下查找log2n次就可以得到結(jié)果。

注意：

1．二分查找是在數(shù)據(jù)有序的情況下才能完成，即進(jìn)行二分查找前數(shù)據(jù)必須先排序。上述框架是以數(shù)據(jù)已從小到大排序?yàn)榍疤釛l件的。

2．這里可能解的范圍為[left,rigth],當(dāng)x＞a[mid]時(shí)，x如果存在的話應(yīng)該是在數(shù)組的[mid+1,right]中，此時(shí)的left改為mid+1，而不是mid；同理，當(dāng)x＜a[mid]時(shí)，x如果存在的話應(yīng)該在數(shù)組的[left,mid-1]里，此時(shí)的right應(yīng)該改為mid-1，而不是mid。

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

left=0;right=n+1;

while(left+1<right)

{

?mid=(left+right)?/?2;

?if (x==a[mid]){ printf("%d",mid);}//查找成功，輸出mid的值并結(jié)束;

?if?(x>a[mid])?left=mid;//往數(shù)組的右邊找

?if?(x<a[mid])?right=mid;//往數(shù)組的左邊找

}

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

二、有相同元素的查找

1、求左側(cè)邊界：

這樣就引申出一個(gè)問題：如何二分查找求左側(cè)邊界。當(dāng)查找的數(shù)字v存在時(shí)，得到它出現(xiàn)的第一個(gè)位置，假如不存在，就得到比它大的第一個(gè)數(shù)的位置。

這樣只要把二分查找修改一下：

為了查找方便，我們在數(shù)組a[0]處插入一個(gè)最小的數(shù)-1，在a[n+1]處插入一個(gè)無窮大數(shù)，left指向0，right指向n+1，這樣解空間為（left,right]。

1、?情況a[mid]>=v時(shí)：right=mid(至少已經(jīng)找到一個(gè)，或者mid可能已經(jīng)是比v大的數(shù)中最小的一個(gè)，或者左邊可能還有比v大的，因此區(qū)間變成（left,mid]。）

2、?情況a[mid]<v時(shí)；left=mid，也就是解只可能在右邊。

例如：

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

第一輪：left=0,right=9,解空間為(0,9]那么mid=(0+9)/2=4,因?yàn)閍[4]=6<7,那么left=mid=4,解空間應(yīng)該是(4,9]。

第二輪left=4,right=9, mid=(4+9)/2=6 ,因?yàn)閍[6]=7==7,那么right=6,也就是解空間為（4,6]。

第三輪?left=4,right=6, mid=(4+6)/2=5 ,因?yàn)閍[5]=7==7,那么right=5,也就是解空間為（4,5]。

因?yàn)榻饪臻g只有一個(gè)解，所以解為下標(biāo)5，所以left+1==right為程序結(jié)束條件。

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

a[n+1]=1000000000;

a[0]=-1;

int findleft(int left,int right,int value)//調(diào)用時(shí)left=0,right=n+1

{

while(left+1<right)??//如果解區(qū)間不止一個(gè)，那么繼續(xù)二分

{

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

???if(a[mid]>=value)//如果找到一個(gè)等于或者大于value的數(shù)，解空間為(left,mid]

??right=mid;

else

???left=mid;?//如果找到一個(gè)小于value的數(shù)，解空間為(mid,right]

}

return right;

}

2、求右側(cè)邊界

如何二分查找求右側(cè)邊界。當(dāng)查找的數(shù)字v存在時(shí)，得到比它大的第一個(gè)數(shù)的位置。

方法如下：

為了查找方便，我們在數(shù)組a[0]處插入一個(gè)最小的數(shù)-1，在a[n+1]處插入一個(gè)無窮大數(shù)，left指向0，right指向n+1，這樣解空間為（left,right]。

1、?情況a[mid]>v時(shí)：right=mid(至少已經(jīng)找到一個(gè)，或者mid可能已經(jīng)是比v大的數(shù)中最小的一個(gè)，或者而左邊可能還有比v大的，因此區(qū)間變成（left,mid]。）

2、?情況a[mid]<=v時(shí)；left=mid，也就是解只可能在右邊。

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

a[n+1]=1000000000;

a[0]=-1;

int findright(int left,int right,int value)//調(diào)用時(shí)left=0,right=n+1

{

while(left+1<right)?//如果解區(qū)間不止一個(gè)，那么繼續(xù)二分查找

{

???int mid=(left+right)/2;

???if(a[mid]<=value)//找到一個(gè)小于或者等于value的數(shù)，解空間為(mid,right)

??left=mid;

else

??right=mid;?//如果找到一個(gè)大于value的數(shù)，解空間為(left,mid)

}

return right;

}

拓展：另外一種二分查找形式找左側(cè)和右側(cè)：

根據(jù)c++的整除是求下界，那么兩個(gè)相鄰的數(shù)求平均數(shù)等于較小的數(shù)，也就是當(dāng)求區(qū)間解時(shí)，當(dāng)左區(qū)間不能滿足要求時(shí)，可以讓left=mid+1，跳出條件變?yōu)長<R，也就是解空間為(L,R]。

找左側(cè)核心程序如下：

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 ");

找右側(cè)核心程序如下：

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 ");

講完知識點(diǎn)，我們來看看幾道習(xí)題

習(xí)題部分

進(jìn)擊的河流

有一個(gè)鐵人三項(xiàng)運(yùn)動(dòng)員，他的弱點(diǎn)是就是游泳，正好他家旁邊有n條流速不同的河流，他想鍛煉m天。
在這m天中，他每天都有不同的體力，他只能在流速小于他體力的河流里游，不然他就會被沖到太平洋(?!!!!!!)。
他想知道每天他能在多少條河里游泳。

輸入格式

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

第二行：n個(gè)數(shù)，分別表示n條河流的流速

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

接下來有m行，分別表示m天中運(yùn)動(dòng)員不同的體力

輸出格式

m行，分別表示運(yùn)動(dòng)員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;
}

?生死狙擊

小飛最近迷上了一個(gè)叫生死狙擊的游戲。不過他的技術(shù)并不好，假設(shè)他的戰(zhàn)斗力是?x。不過，他的戰(zhàn)斗力是由心情來定的，每天都不同?，F(xiàn)有一群(1<=n<=100000)也是玩生死狙擊的朋友，他們也有戰(zhàn)斗力。小飛想找一些比自己強(qiáng)的人玩，提高自己的戰(zhàn)斗力，如：小燁，小祖，小明等。
小飛一共玩了m天，假設(shè)其他人的戰(zhàn)斗力不變。問：小飛每天可以找到多少比自己強(qiáng)的人。

輸入格式

第一行輸入一個(gè)n，表示有n個(gè)朋友；(1<=n<=100000)
第二行輸入n個(gè)朋友的戰(zhàn)斗力；每個(gè)朋友戰(zhàn)斗力不超過longint;（已有序）；
第三行輸入一個(gè)m，表示有m天；(1<=m<=100000)
接下來m行，表示小飛每天的戰(zhàn)斗力；小飛戰(zhàn)斗力不超過longint;

輸出格式

共m行，每一行小飛每天找到的人數(shù)；

輸入/輸出例子

輸入：

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;
}

選人

在一條坐標(biāo)軸上，有Ｎ頭奶牛，第i頭奶牛的位置是Xi。FJ現(xiàn)在要選出三頭奶牛去比賽，不妨假設(shè)選擇了奶牛a,b,c。那么必須要滿足：

1、Xa < Xb < Xc。

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

你的任務(wù)是計(jì)算，F(xiàn)J總共有多少種不同的選擇？

輸入格式

第一行，一個(gè)整數(shù)N。 3 <= N <= 1000。 接下來有N行，第i行是整數(shù)Xi。

輸出格式

一個(gè)整數(shù)。

輸入/輸出例子

輸入：

5?
3?
1?
10?
7?
4

輸出：

4

樣例解釋

可以有4種不同的選擇，每種選擇對應(yīng)的3頭奶牛的坐標(biāo)是： {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;
}

能不能留下關(guān)注和點(diǎn)贊........

安慰一下啥也不會的小學(xué)生..........文章來源地址http://www.zghlxwxcb.cn/news/detail-857271.html

到了這里，關(guān)于二分查找知識點(diǎn)及練習(xí)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！