789. 数的范围 （二分学习）

1.确定一个区间，使得目标值一定在区间中

2.找一个性质满足：

        （1）性质具有二段性

        （2）答案是二段性的分界点

3.整数二分（处理红色右端点和绿色左端点）

//代码1：右端点
int l=0,r=n;
while(l < r){
    int mid = (l+r+1) >> 1;
    if(在红色段){
        l = mid;
    }
    else r = mid - 1;
}

//代码2：左端点绿色
if是绿的，说明ans在【了，m】
int l=0,r=n;
while(l<r){
    int mid = l+r >> 1;
    if(是绿的){
        r = mid;
    }
    else l = mid + 1;
}

例题：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;

int n,k;
int a[100010];

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    
    while(k--){
        int q;
        scanf("%d",&q);
        //找区间左端点
        int l=0,r=n-1;
        while(l<r){
            int mid = l+r >> 1;
            if(a[mid] >= q)//中位数大于q，说明右端点在左半段
            {
                r = mid;
            }
            else l = mid + 1;
        }
        if(a[l] == q){
            cout<<l<<" ";
            //右端点
            l = 0,r = n-1;
            while(l < r){
                int mid = (l + r + 1) >> 1;
                if(a[mid] <= q){
                    l = mid;
                }
                else r = mid - 1;
            }
            if(a[l] == q){
                cout<<l<<endl;
            }
        }
        else {
            cout<<"-1 -1"<<endl;
        }
    }
    return 0;
}