历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

二分查找的各种模板

作者：

江见月 , 2021-04-21 13:46:07 , 所有人可见 , 阅读 570

二分查找的各种模板

算法简介

二分查找是二分法的一种应用，用来解决有序区间的元素查找问题。

每次判断区间中点，根据判断结果可以区间缩小一半，最终锁定答案。

二分法思路简单，但是根据查找需求有不同的模板,里面的细节需要注意。

算法模板

模板1：要找的数字一定存在时而且唯一的时候

//二分查找 
#include <iostream>
using namespace std;
int binarySearch(int a[],int l,int r,int x)//递归
{
    if(l<=r)
    {
        int mid=(r+l)/2;
        if(a[mid]>x) return binarySearch(a,l,mid-1,x);
        if(a[mid]<x) return binarySearch(a,mid+1,r,x);
        if(a[mid]==x) 
        {
            return mid;
        }
    }
}
int binarySearch(int a[],int l,int r,int ch)//非递归
{
    int mid=(l+r)/2;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(a[mid]==ch)
        {
            return mid;
        }
        else if(a[mid]<ch)
        {
            l=mid+1;
        }else{
            r=mid-1;
        }
    }

}

int main(){
    int n,a[100],x;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cin>>x;
    cout<<binarySearch(a,1,n,x);
    return 0;
}

模板2：要找的数字一定存在时但是可能有多个时

这种情况下，我们需要查询的一般是元素第一次或者最后一次出现的位置

这时候我们一般是二分到区间从一个范围缩成一个点

1.查目标元素第一次出现的位置

/*
测试数据1 输出 2  
5
1 3 3 3 9  
3
*/
//二分查找（返回第一次出现的位置 ） 
#include <iostream>
using namespace std;
int binarySearch(int a[], int l, int r, int x)
{
    int mid;
    while(l < r)
    {
        mid = (l + r ) / 2;
        if(a[mid] == x)//发现目标 在（l,mid]区间接着查询 
            r = mid;
        else if(a[mid] < x)
            l = mid+1;  
        else if(a[mid] > x)
            r = mid-1;
    }
    return l;
}
int main()
{
    int n, a[100], x;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cin >> x;
    cout << binarySearch(a, 1, n, x);
    return 0;
}

2.查目标元素最后一次出现的位置

//二分查找（返回最后一次出现的位置 ）
/*
测试数据 输出 4  
5
1 3 3 3 9  
3
*/ 
#include <iostream>
using namespace std;
/*
    这里需要注意 mid = (l + r + 1) / 2 这里
    当 l = 2 r = 3 且 a[l]==x 时 会陷入死循环 所以需要+1
    可以这么记：找到x元素后我们区间 mid 继续变大 
    mid变大就是让mid 右移  右移就需要+1

*/
int binarySearch(int a[], int l, int r, int x)
{
    int mid;
    while(l < r)
    {
        mid = (l + r + 1) / 2;// l = 2 r = 3会陷入死循环 需要 + 1 
        if(a[mid] == x)
            l = mid;
        else if(a[mid] < x)
            l = mid+1;  
        else if(a[mid] > x)
            r = mid-1;
    }
    return l;
}
int main()
{
    int n, a[100], x;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cin >> x;
    cout << binarySearch(a, 1, n, x);
    return 0;
}

模板3：要找的数字可能存在也可能有多个的时候

这个时候我们可以把数组大致分成三段：小于目标数字的等于目标数字的，大于目标数字的

1.当需要找数字第一次的位置或者第一个大于目标数字的元素下标

我们可以在红黄区域中间划线

)

这样的话区间被分成两段红色区域（<）和黄绿色区域（>=）

查第一次出现得位置查找的数字不存在时结果是第一个大于目标数字的元素下标

/*
测试数据1 输出 2 （查数字第一次出现的位置） 
5
1 3 3 3 9  
3

测试数据2 输出 4 （查的数字不存在 结果是第一个大于目标数字的元素下标） 
4
1 3 5 7
6

*/
//二分查找
#include <bits/stdc++.h>
using namespace std;
int n,a[100010],x,m;
//左边界（第一次出现得位置）查找的数字不存在 结果是第一个大于目标数字的元素下标 
int binarySearch(int a[],int l,int r,int x){
    int mid;
    while(l<r){
        mid=(l+r)/2;
        //是否是黄绿色区域 是的话从(l,mid)继续找
        if(a[mid]>=x){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    return l;

}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&x);
    printf("%d ",binarySearch(a,1,n,x));
    return 0;
}

2. 当需要找数字最后一次的位置或者最后一个小于目标数字的元素下标

我们可以在黄绿区域中间划线

这样的话区间被分成两段红黄色区域（<=）和绿色区域（>）

/*
测试数据1 输出 4  查最后一次出现的位置 
5
1 3 3 3 9  
3

测试数据2 输出 3 查最后一个小于目标数字的 
4
1 3 5 7
6

*/
//二分查找（非递归） P2249
#include <bits/stdc++.h>
using namespace std;
int n,a[100010],x,m;
//右边界 （最后一次出现的位置）从左往右 查找的数字不存在 结果是最后一个小于目标数字的 元素下标 
int binarySearch(int a[],int l,int r,int x){
    int mid;
    while(l<r){
        mid=(l+r+1)/2;//l=2 r=3会陷入死循环 需要+1 
        //是否是红黄区域 是的话从(mid,r)继续找 
        if(a[mid]<=x){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    return l;   
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&x);
    printf("%d ",binarySearch(a,1,n,x));
    return 0;
}