[AcWing 789]数的范围

#include<iostream>
using namespace std;

const int N = 100010;
int n, m;
int q[N];

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> q[i];
    while(m--){
        int x;
        cin >> 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;
            }
        }//模板r = mid
        
        if(q[l] != x){
            cout << "-1 -1" << endl; //数组中不存在元素x
        }
        else{
            cout << l << ' '; //元素x的起始位置
            
            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;
                }
            }//模板l = mid
            
            cout << l << endl; //元素x的终止位置
        }
        
    }
    
    return 0;
} 


/*
整数二分：
本质并不是单调性
但与单调性的关系是：
如果有单调性则一定可以二分
但可以二分的题目不一定非得有单调性

本质是边界
找到一个性质
整个区间一分为二
左半边不满足性质 右半边满足性质
可以找到分界处的两个边界点
 对应两个模板

第一种情况：想二分左半边的边界点时
mid = (L+R+1) / 2      //加1是为了防止死循环
if(check(mid))
	情况 答案新区间    更新
	true    [mid,R]           L=mid
	false    [L,mid-1]        R=mid-1
模板：
//区间[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;
}


第二种情况：想二分右半边的边界点时
mid = (L+R) / 2
if(check(mid))
	情况 答案新区间    更新
	true    [L,mid]           R=mid
	false    [mid+1,R]      L=mid+1
模板：
//区间[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;
		else l = mid+1;
	}
	return l;
}

二分的模板是一定要保证有解的
原本的题是可以无解的 二分不用考虑无解

方法：
先写一个mid 
随便先想一个check函数（想清楚性质）
根据check函数的值想一下答案是怎么去划分的
选择答案所在的区间
true 时答案在哪个边界里面
false时答案在哪个边界里面
更新时是L=mid还是R=mid
确定求mid处是否需要补上+1

*/