二分查找
例题 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） (leetcode-cn.com)
二分查找模板
第一种
//第一个大于等于target的位置
int bina1(vector<int> & n , int tar){ int l=0 ,r=n.size()-1; while(l<r){ int mid = (r+l )/2; if(n[mid]<tar) l=mid+1; else r=mid; } return n[l]==tar ? l:-1;//没有找到返回-1； }
第二种
//找到最后一个小于等于target的位置
int bina2(vector<int> & n , int tar){ int l=0,r=n.size()-1; while(l<r){ int mid=(r+l+1)>>1; if(n[mid]>tar) r=mid-1; else l=mid; } return n[l]==tar? l: -1; }
模板记忆
第一步初始化 l ，r 第二步 while循环和结束条件（l<r）,第三步return
关键在于两个可以修改的位置，第一if 保证剩余的区间满足条件，第二mid的取值，保证能退出循环。