二分查找模板

1. 划分区间，确定check(mid)
2. 根据区间来得出l,r的值
   若为a[mid]<x或a[mid]<=x形式，则先用l= xxx;
   若为a[mid]>x或a[mid]>=x形式，则先用r=xxx;
3. 确定mid，若r=mid，则mid=(l+r)/2, 如l=mid,则mid=(l+r+1)/2;

本题用 a=[1,2,2,3,3,5,5],x=3为代表来举例(a默认有序)。

1.第一个大于等于x的数的位置

1. 划分区间
   check(mid)为 a[mid]>=x，
   [1,2,2,3,3,5,5]可分为两部分[1,2,2]与[3,3,5,5]

2. 根据区间得出l,r的值
   若a[mid]>=x成立,则r=mid(此处r有可能取到mid);
   反之,则l=mid+1

3. 确定mid
   因为r=mid，则mid=(l+r)/2

int l=0,r=m-1;
while(l<r){
    int mid=l+r>>1;
    if(a[mid]>=x) r=mid;
    else l=mid+1;
}

2. 第一个大于x的数的位置

1. 划分区间
   check(mid)为a[mid]>x
[1,2,2,3,3,5,5]可分为两部分[1,2,2,3,3]与[5,5]

2. 根据区间得出l,r的值
   若a[mid]>x,则r=mid(r有可能取到第一个>x的位置)
   反之，则l=mid+1

3. 确定mid
   因为r=mid,则mid=(l+r)/2

int l=0,r=m-1;
while(l<r){
    int mid=l+r>>1;
    if(a[mid]>x) r=mid;
    else l=mid+1;
}

3.第一个小于x的数的位置

1. 划分区间
   check(mid)为a[mid]<x
[1,2,2,3,3,5,5]可分为两部分[1,2,2]与[3,3,5,5]

2. 根据区间得出l,r的值
   若a[mid]<x，则l=mid；
   反之r=mid-1

3. 确定mid
   因为l=mid，则mid=(l+r+1)/2

int l=0,r=m-1;
while(l<r){
    int mid=l+r+1>>1;
    if(a[mid]<x) l=mid;
    else r=mid-1;
}

4.最后一个大于等于x的位置

这里可转化为第一个小于x+1的位置（和第二种类似）

int l=0,r=m-1;
while(l<r){
     intmid=l+r+1>>1;
     if(a[mid]<x+1) l=mid;
     else r=mid-1;
 }

也可以用其他的方法

1. 划分区间
   check(mid)为a[mid]<=x
[1,2,2,3,3,5,5]可分为两部分[1,2,2,3,3]与[5,5] （注意此处与第一种情况的不同）

2. 根据区间得出l,r的值
   若a[mid]<=x，则l=mid；
   反之r=mid-1

3. 确定mid
   因为l=mid，则mid=(l+r+1)/2

int l=0,r=m-1;
while(l<r){
    int mid=l+r+1>>1;
    if(a[mid]<=x) l=mid;
    else r=mid-1;
}