二分查数+二分模板

妖狐艹你老母 2023-09-30 11:06 19阅读 0赞

定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。

对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 00 开始计数）。

如果数组中不存在该元素，则返回 `-1 -1`。

##### 输入格式 #####

第一行包含整数 nn 和 qq，表示数组长度和询问个数。

第二行包含 nn 个整数（均在 1∼100001∼10000 范围内），表示完整数组。

接下来 qq 行，每行包含一个整数 kk，表示一个询问元素。

##### 输出格式 #####

共 qq 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 `-1 -1`。

##### 数据范围 #####

1≤n≤1000001≤n≤100000  
1≤q≤100001≤q≤10000  
1≤k≤100001≤k≤10000

##### 输入样例： #####

6 3
    1 2 2 3 3 4
    3
    4
    5

##### 输出样例： #####

3 4
    5 5
    -1 -1

题解：下图  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiD5a-75YyX6YeM_size_20_color_FFFFFF_t_70_g_se_x_16]  
注意：当q\[l\]!=x的时候表示在该数组中为找到这个x值  
第一个循环也是如此，不过if条件变为 q\[mid\]<=x，思想一致

#include<iostream>
    using namespace std;
    
    const int N=1e6+10;
    int n,m;
    int q[N];
    
    int main(){
        
        scanf("%d%d",&n,&m);
        for(int i= 0;i<n;i++) scanf("%d",&q[i]);
        
       
        while(m--){
        
            int x;
            scanf("%d",&x);
         
            int l=0,r=n-1;
            while(l<r){
        
                int mid=l+r >> 1;
                if(q[mid]>=x) r=mid;
                else l=mid+1;
            }
            if(q[l]!=x) cout<<"-1 -1"<<endl;
            else{
        
                cout<<l<<" ";
                int l=0,r=n-1;
                while(l<r){
        
                    int mid=l+r+1 >> 1;
                    if(q[mid]<=x) l=mid;
                    else r=mid-1;
                }
                cout<<l<<endl;
            }
            
            
        }
        return 0;
        
    }

二分模板

bool check(int x) {
        /* ... */} // 检查x是否满足某种性质
    
    // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
    int bsearch_1(int l, int r)
    {
        
        while (l < r)
        {
        
            int mid = l + r >> 1;
            if (check(mid)) r = mid;    // check()判断mid是否满足性质
            else l = mid + 1;
        }
        return l;
    }
    // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
    int bsearch_2(int l, int r)
    {
        
        while (l < r)
        {
        
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }
    
    作者：yxc
    链接：https://www.acwing.com/blog/content/277/
    来源：AcWing
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiD5a-75YyX6YeM_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/6e7d7db499214671877b0e6d9ee9a489.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiD5a-75YyX6YeM,size_20,color_FFFFFF,t_70,g_se,x_16