二分查找模板：

能够二分的情况：

1）l,r区间之间单调，一般分为两种：

一：直接二分某一段自然数

二：二分单调数组（如下演示）

如模板所示数组

a[] = {0,0,0,1,1,2,3,4,4,4,4,5,8};

共有n = 13个数。

第一种情况返回结果为：查找到的最左边答案，没有查找到的最右边答案。

第二种情况返回结果为：查找到的最右边答案，没有查找到的最左边答案。

输入样例：

0输出样例：

0 2
输入样例：

6输出样例：

12 11

代码：

• 
  
  #include<iostream>
  
  
• 
  
  #include<bits/stdc++.h>
  
  
• 
  
  using namespace std;
  
  
• 
  
  //算法在做闭右开的区间内进行查找
  
  
• 
  
  //如果所有的元素都比find小，则返回值越界
  
  
• 
  
  int main(){
  
  
• 
  
      int a[] = {0,0,0,1,1,2,3,4,4,4,4,5,8};
  
  
• 
  
      int n = 13;
  
  
• 
  
      int l,r;
  
  
• 
  
      int find;
  
  
• 
  
      while(cin>>find){
  
  
• 
  
          //ok_left,no_right
  
  
• 
  
          l = 0;r = n;
  
  
• 
  
          while(l<r){
  
  
• 
  
              int mid = (l+r)/2;
  
  
• 
  
              if(a[mid]>=find) r = mid;
  
  
• 
  
              else l = mid+1;
  
  
• 
  
          }
  
  
• 
  
          cout<<l<<endl;
  
  
• 
  
          //no_left,ok_right
  
  
• 
  
          l = 0;r = n;
  
  
• 
  
          while(l<r){
  
  
• 
  
              int mid = (l+r-1)/2+1;
  
  
• 
  
              if(a[mid]<=find) l = mid;
  
  
• 
  
              else r = mid-1;
  
  
• 
  
          }
  
  
• 
  
          cout<<l<<endl;
  
  
• 
  
          //ok_left,no_right
  
  
• 
  
          cout<<lower_bound(a,a+n,find) - a<<endl;
  
  
• 
  
          //ok_right+1,no_right
  
  
• 
  
          cout<<upper_bound(a,a+n,find) - a<<endl;
  
  
• 
  
      }
  
  
• 
  
  }
  
  
  

其实二分并不需要严格记忆：

当需要二分时，假设l = 1，r = 3；然后分别假设1,2,3为需要的答案，如果1,2,3均能够取到且返回答案正确，说明二分正确。就是这么简单。

很不错，受教了