前言

这是一道牛客周赛的C题，题目用到了二分的知识，在这里总结一下。 https://ac.nowcoder.com/acm/contest/120553/C

一、题目描述

大概就是给以你一个数，让你在一个很多个区间找这个数是否在给的区间里面。 整体的思路就是 先把区间左端点排序，然后二分查找最后一个满足大于x的区间左端点。

二、代码分析

1.整体代码

代码如下（示例）：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Interval {
    int l, r, idx;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    
    vector<Interval> range(n);
    for(int i = 0; i < n; i++){
        cin >> range[i].l >> range[i].r;
        range[i].idx=i+1;
    }
    
    sort(range.begin(),range.end(),[](Interval a, Interval b) {
        return a.l < b.l;
    });
    
    
    for(int k = 0; k < q; k++){
        int x;
        cin >> x;
//      bool is_ok = false;
//      int tmp = 0;
        
        //二分
        int left=0;
        int right=n-1;
        int ans=-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(range[mid].l <= x){
                ans=mid;
                left=mid+1;
            }else{
                right=mid-1;
            } 
        }
        
        if(ans!=-1 && range[ans].r>=x && x >= range[ans].l){
            cout << range[ans].idx << endl;
        }else{
            cout << -1 << endl;
        }
        
        
        
        //使用二维数组枚举就是常规思路，最终结果会超时，所以不能使用
//         for(int i = 0; i < n; i++){
//             if(x >= range[i][0] && x <= range[i][1]){
//                 is_ok = true;
//                 tmp = i;
//                 break;
//             }
//         }
        
//         if(is_ok){
//             cout << tmp + 1 << endl;
//         } else {
//             cout << -1 << endl;
//         }
    }
    return 0;
}

2.单独分析

代码如下（示例）：

		int left=0;
        int right=n-1;
        int ans=-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(range[mid].l <= x){
                ans=mid;
                left=mid+1;
            }else{
                right=mid-1;
            } 
        }

显而易见，二分第一步就要声明左右指针left和right； 然后while(左<=右)也很容易写出； 别忘了声明mid，为两指针相加除二后的位置； 接下来if这里就开始饶了：到底怎么写条件呢？

首先我们得知道，mid指针始终是表示的是我们要找的左端点的可能值，而x是固定死的，他不能动，所以我们的思路应该是用左端点去和x比较，而不是用x去找左端点。然后下面举例理解会好点。

假如x=6,[3,4],[5,6],[8,9]； 因为我们要找的是左端点，所以是在3,5,8中二分； 我们的目标是找x是不是在区间里面，所以我们判断停止的条件一定是： mid指向的值 要小于我们的x。这里就是我们的mid指向的左端点要小于6，你好好想想，如果最后停下的时候mid左端点都大于6了，那我们还找啥，他一定是不在区间里面的。

在这个例子里面体现就是你找到的mid是8,8>6，而6不在左端点为8的区间里面，我们要的mid是5，刚好停在了6的左边，达到了我们二分的目的。

所以判断停下的代码就是

 if(range[mid].l <= x){
 	ans=mid;
 }

那又有人要问了：诶这ans=mid;为什么跟在判断后面？ 显而易见，在哪停下答案就是多少，mid停止的时候就是我们要的答案，我们要保证mid在x的左边，那就必须在条件判断<=x的时候让mid=ans。

然后就是为什么要left=mid+1，right=mid-1而不是直接让左右指针直接等于mid呢? 有两个数3,4 ，left=0,right=1,mid=(0+1)/2=0,left还是=mid=0...导致死循环。

ok,根据上面的情况我们可以总结出第二种情况 1).第一种情况：

if(左边最后一个要找的数[mid] <= x){
      	 ans=mid;
      	 left=mid+1;
      }else{
         right=mid-1;
      } 

2).第二种情况：

if(右边边第一个要找的数[mid] >= x){
      	 ans=mid;
      	 right=mid-1;
      }else{
         left=mid+1;
      } 

不要忘记这两种情况的左右指针代码的位置要换一下...

总结

二分其实就是判断这里要纠结一下，具体的情况看是要找值x的 左最后 还是 右第一 满足条件的值。

新手第一次写这种算法的博客，可能说的比较乱，以后会一点点精进的XD