基本模板

  1. int binSearch(vector<int>& nums, int target) {
  2.         int lo=0;
  3.         int hi=(...)//key 1
  6.         while(...){ //key 2 
  7.             int mi=lo+((hi-lo)>>1);
  8.             if(nums[mi]<target){
  9.                 (...)//key3
  11.             }else if(nums[mi]==target){
  12.                 (...)//key3
  14.             }else if(nums[mi]>target){
  15.                 (...)//key3
  17.             }
  18.         }
  19.         return (...);
  20.     }

version 1

  1. int binSearch(vector<int>& nums, int target) {
  2.         int lo=0;
  3.         int hi=nums.size()-1;//key 1: 因为是左闭右闭区间
  6.         while(lo<=hi){ //key 2 :左闭右闭区间 [lo, hi]，判断结束的条件！
  7.             int mi=lo+((hi-lo)>>1);
  8.             if(nums[mi]<target){
  9.                 lo=mi+1;
  10.                 //[mi+1,hi] 
  11.             }else if(nums[mi]==target){
  12.                 return mi;
  13.                 //命中返回
  14.             }else if(nums[mi]>target){
  15.                 hi=mi-1;
  16.                 //[lo,mi-1]
  17.             }
  18.         }
  19.         return -1;
  20.     }

:::tips

  1. 左闭右闭区间
    1. 右边界可以取到，所以一开始是nums.size()-1
    2. 判断命中即返回，有缺陷，找到的并不是右边第一个数或是左边第一个数
    3. 更新时的区间需要排除mid ::: 左闭右开区间版本 ```cpp int binSearch(vector& nums, int target) { int lo=0; int hi=nums.size();//key 1: 因为是左闭右开
  1.     while(lo<hi){ //key 2 :左闭右闭区间 [lo, hi]，判断结束的条件！
  2.         int mi=lo+((hi-lo)>>1);
  3.         if(nums[mi]<target){
  4.             lo=mi+1;
  5.             //[mi+1,hi)
  6.         }else if(nums[mi]>=target){
  7.             hi=mi;
  8.             //[lo,mi)
  9.         }
  10.     }
  11.     return nums[lo]==target?lo:-1;
  12. } 
  1. <a name="zWo2X"></a>
  2. # 寻找左侧边界的二分搜索
  3. ```cpp
  4. int binSearch(vector<int>& nums, int target) {
  5.         int lo=0;
  6.         int hi=nums.size();//key 1: 因为是左闭右开
  9.         while(lo<hi){ //key 2 :左闭右闭区间 [lo, hi)，判断结束的条件！
  10.             int mi=lo+((hi-lo)>>1);
  11.             if(nums[mi]==target){
  12.                 hi=mi;//key!
  13.             }else if(nums[mi]<target){
  14.                 lo=mi+1;
  15.                 //[mi+1,hi)
  16.             }else if(nums[mi]>target){
  17.                 hi=mi;
  18.                 //[lo,mi)
  19.             }
  20.         }
  21.     if(lo>nums.size()) return -1;
  22.         return nums[lo]==target?lo:-1;
  23.     }

找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间[left, mid) 中继续搜索,即不断向左收缩，达到锁定左侧边界的目的。

寻找右边界

  1. int binSearch(vector<int>& nums, int target) {
  2.         int lo=0;
  3.         int hi=nums.size();//key 1: 因为是左闭右开
  6.         while(lo<hi){ //key 2 :左闭右闭区间 [lo, hi)，判断结束的条件！
  7.             int mi=lo+((hi-lo)>>1);
  8.             if(nums[mi]==target){
  9.                 lo=mi+1;//key!
  10.             }else if(nums[mi]<target){
  11.                 lo=mi+1;
  12.                 //[mi+1,hi)
  13.             }else if(nums[mi]>target){
  14.                 hi=mi;
  15.                 //[lo,mi)
  16.             }
  17.         }
  18.     if(lo==0) return -1;
  19.     return nums[lo-1]==target?lo-1:-1;
  20.     }

左闭右闭区间

  1. int findLe(vector<int>& nums, int target){
  2.         int lo=0;
  3.         int hi=nums.size()-1;
  4.         while(lo<=hi){
  5.             int mi=lo+((hi-lo)>>1);
  6.             if(nums[mi]==target){
  7.                 hi=mi-1;
  8.             }else if(nums[mi]<target){
  9.                 lo=mi+1;
  10.             }else if(nums[mi]>target){
  11.                 hi=mi-1;
  12.             }
  13.         }
  14.         if(lo>=nums.size()||nums[lo]!=target) return -1;
  15.         return lo;
  17.     }
  18.     int findRi(vector<int>& nums, int target){
  19.         int lo=0;
  20.         int hi=nums.size()-1;
  21.         while(lo<=hi){
  22.             int mi=lo+((hi-lo)>>1);
  23.             if(nums[mi]==target){
  24.                 lo=mi+1;
  25.             }else if(nums[mi]>target){
  26.                 hi=mi-1;
  27.             }else if(nums[mi]<target){
  28.                 lo=mi+1;
  29.             }
  30.         }
  31.         if(hi<0||nums[hi]!=target) return -1;
  32.         return hi;//lo-1;
  33.     }

左闭右开区间

  1. int findRi(vector<int>& nums, int target) {
  2.         int lo=0;
  3.         int hi=nums.size();
  4.         while(lo<hi){
  5.             int mi=lo+((hi-lo)>>1);
  6.             if(nums[mi]==target){
  7.                 lo=mi+1;
  8.             }else if(nums[mi]<target){
  9.                 lo=mi+1;
  10.             }else if(nums[mi]>target){
  11.                 hi=mi;
  12.             }
  13.         }
  14.         if(hi==0) return -1;
  15.         return nums[lo-1]==target?lo-1:-1;
  16.     }
  18.     int findLe(vector<int>& nums, int target) {
  19.         int lo=0;
  20.         int hi=nums.size();
  21.         while(lo<hi){
  22.             int mi=lo+((hi-lo)>>1);
  23.             if(nums[mi]==target){
  24.                 hi=mi;
  25.             }else if(nums[mi]>target){
  26.                 hi=mi;
  27.             }else if(nums[mi]<target){
  28.                 lo=mi+1;
  29.             }
  30.         }
  31.         if(lo==nums.size()) return -1;
  33.         return nums[lo]==target?lo:-1;
  34.     }