一、概述

1. 通常关于二分模板有两套模板，以如下数据为例:

9 5 1 3 4 5 5 5 7 9 10

当我们从队列查找5的位置

• 左边界：查找index=3

• 右边界：查找index=5

• 二分查找为什么总是写错？哔哩哔哩_bilibili

具体步骤:

• 我们将一个有序数列看做红蓝两部分，前面是红，后面是蓝，那么l与r之间的部分就是待定义的红蓝区间
• 决定返回的l还是r

二、模板

1. 查找左边界

2. main.cpp

   ```
   #include [HTML_REMOVED]

   using namespace std;

   int arr[10];

   int binSearch(int len,int target){
   int l=-1,r=len; //由于初始不确定头和尾是处于哪个边界，因此我们置值在外
   while(l+1!=r){ //由红蓝的划分可知，最后划分的结果必然是l+1=r
   int m=l+r>>1;
   if(arr[m]<target){ //取左边红色边界的条件
   l=m;
   }else{
   r=m;
   }
   }
   return r;
   }

   int main(){
   int len,target;
   cin >> len >> target;
   for(int i=0;i[HTML_REMOVED]> arr[i];
   }
   int res = binSearch(len,target);
   cout << “res:” << res << endl;
   return 0;
   }
   ```

3. 结果:3

4. 结论

   • 我们将数列分为两部分:
   • 红方:1 2 3 4
   • 蓝方:5 5 5 7 9 10
   • 显然最终arr[l]=4.arr[r]=5,故返回r

5. 查找右边界

6. main.cpp

   ```
   #include [HTML_REMOVED]

   using namespace std;

   int arr[10];

   int binSearch(int len,int target){
   int l=-1,r=len; //由于初始不确定头和尾是处于哪个边界，因此我们置值在外
   while(l+1!=r){ //由红蓝的划分可知，最后划分的结果必然是l+1=r
   int m=l+r>>1;
   if(arr[m]>target){ //取右边蓝色边界的条件
   r=m;
   }else{
   l=m;
   }
   }
   return l;
   }

   int main(){
   int len,target;
   cin >> len >> target;
   for(int i=0;i[HTML_REMOVED]> arr[i];
   }
   int res = binSearch(len,target);
   cout << “res:” << res << endl;
   return 0;
   }
   ```

7. 结果:5

8. 结论:类似上