mid 最好写成 mid = left + ( right - left ) / 2 以防止溢出

左侧边界

P1894 - 二分查找左侧边界

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     int n,a[100005],q;
  5.     scanf("%d",&n);  //输入数组元素个数
  6.     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  7.     scanf("%d",&q);  //输入询问次数
  8.     while(q--){  //循环q次
  9.         int t,l=1,r=n;
  10.         scanf("%d",&t);
  11.         //核心
  12.         while(l<=r){
  13.             int mid=l+(r-l)/2;
  14.             if(a[mid]>=t) r=mid-1;
  15.             else l=mid+1;
  16.         }
  17.         if(a[l]!=t) l=-1;  //若查找的数不存在，输出-1
  18.         printf("%d ",l);
  19.     }
  20.     return 0;
  21. }

lower_bound()

lower_bound ( first , last , val ) 用来查找 [ first , last ) 范围内第一个大于或等于val的元素的位置。如果是数组，返回该位置的指针；如果是容器，返回该位置的迭代器。若查找失败，返回 last 。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     int n,a[100005],q;
  5.     scanf("%d",&n);
  6.     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  7.     scanf("%d",&q);
  8.     while(q--){
  9.         int t;
  10.         scanf("%d",&t);
  11.         int* i=lower_bound(a+1,a+n+1,t);
  12.         if(*i!=t) i=a-1;
  13.         printf("%d ",i-a);
  14.     }
  15.     return 0;
  16. }

右侧边界

P1895 - 二分查找右侧边界

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     int n,a[100005],q;
  5.     scanf("%d",&n);  //输入数组元素个数
  6.     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  7.     scanf("%d",&q);  //输入询问次数
  8.     while(q--){  //循环q次
  9.         int t,l=1,r=n;
  10.         scanf("%d",&t);
  11.         //核心
  12.         while(l<=r){
  13.             int mid=l+(r-l)/2;
  14.             if(a[mid]<=t) l=mid+1;
  15.             else r=mid-1;
  16.         }
  17.         if(a[r]!=t) r=-1;  //若查找的数不存在，输出-1
  18.         printf("%d ",r);
  19.     }
  20.     return 0;
  21. }

upper_bound()

upper_bound ( first , last , val ) 用来查找 [ first , last ) 范围内第一个大于val的元素的位置。如果是数组，返回该位置的指针；如果是容器，返回该位置的迭代器。若查找失败，返回 last 。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     int n,a[100005],q;
  5.     scanf("%d",&n);
  6.     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  7.     scanf("%d",&q);
  8.     while(q--){
  9.         int t;
  10.         scanf("%d",&t);
  11.         int* i=upper_bound(a+1,a+n+1,t);
  12.         i--;
  13.         if(*i!=t) i=a-1;
  14.         printf("%d ",i-a);
  15.     }
  16.     return 0;
  17. }

二分答案

可以用于解决求最大值最小或最小值最大的问题
应用：防御迷阵、跳石头等
自己总结的一种用法：如果mid可能在查找范围内，可以先让左指针移到mid+1的位置，最后返回 L-1