二分查找使用前提：有序数组
用红蓝染色法理解二分查找数组中>=某个数的区间(闭区间写法)
定义红色区间表示<target的区间，蓝色区间表示>=target的区间，[left,right]区间是还未确定的区间
采用闭区间的写法，初始时闭区间范围为[0,n-1],即所有数都不确定，接着取中间下标mid，判断mid和target的大小关系，若mid比target小，那么说明mid左边所有数都比target小，因此mid及mid左边所有数都可标记为红色
如图target=8,第一次查找时mid=2,对应值为7<8,则说明mid左边所有数都小于target，标记为红色,改变未确定区间为[mid+1,right]
第二次查找mid=4,对应的值大于等于8,则右边所有值都可以确定大于等于8,标记为蓝色,未确定区间变为\[left,mid-1]
一直重复上述过程就可以将整个数组划分为红色和蓝色区间，而且可以知道每次循环结束后红色区间的结束位置为left-1,蓝色区间的开始位置为right+1，因此可以得到结论以闭区间的方式划分最后得到大于等于target的区间一定是在right+1的位置的。最后未确定的区间为空，要想让[left,right]为空，left=right+1,所以循环结束的条件就是left<=right，第一个>=target的位置就是left或者right+1
此外还需注意一些细节：
1. 若left和right都可能大于整形的范围的一半，所以会数值溢出，处理方法是写出mid = left +(right-left)/2的形式防止溢出
2. 若数组中的数都比target小，left最后会等于数组长度;除了这种情况外,数组里面可能还是没有等于target的值,因此最后找到的下标对应的值也不会等于target
闭区间写法：
int binarySearch(vector<int> v,int target){//查找大于等于的数的闭区间写法
int left=0;
int right=v.size(); //半开半闭区间[0,n)
while(left<=right){ //闭区间[left,right],left可以等于right
int mid = left +(right-left)/2; //避免right+left溢出
if(v[mid]<target){
left=mid+1; //区间变为[mid+1,right]
}else{
right=mid-1; //[left,mid-1]
}
}
return left; //或者right+1
}
半开半闭和开区间的写法(以左闭右开为例)
1. 若为左闭右开，开始时未确定的区间就是[0,n),也就是right开始时为n
2. 比较完mid后left依然变成mid+1,但右边变成了开区间，所以right就变成mid就行
3. 区间[left,right)最终为空条件为left=right,所以循环的条件就是left<right,最后left会等于right,并且第一个大于等于target的数就在right/left位置
int binarySearch(vector<int> v,int target){//查找大于等于的数的闭区间写法
int left=0;
int right=v.size(); //区间[0,n)
while(left<right){ //区间[left,right)为空停止
int mid = left +(right-left)/2; //避免right+left溢出
if(v[mid]<target){
left=mid+1; //区间变为[mid+1,right)
}else{
right=mid; //[left,mid)
}
}
return right;
}开区间
1. 初始时left=-1,right=n
2. 比较完mid后left=mid或者right=mid
3. 区间(left,right)最终为空条件为left+1=right,所以**循环的条件就是left+1\<right**,最后left+1=right,并且第一个大于等于target的数就在right位置
int binarySearch(vector<int> v,int target){//查找大于等于的数的闭区间写法
int left=-1;
int right=v.size(); //开区间(-1,n)
while(left+1<right){ //开区间(left,right)为空停止
int mid = left +(right-left)/2; //避免right+left溢出
if(v[mid]<target){
left=mid; //区间变为(mid,right)
}else{
right=mid; //(left,mid)
}
}
return right;
}其余情况：找 >、<=、< 的情况
- 大于x: 在整数的条件下相当于>=x+1
- 小于x: 看成>=x的第一个数左边的那个数
- 小于等于x: 转换成大于x(>=x+1)的左边的数
[34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/)
[2529. 正整数和负整数的最大计数](https://leetcode.cn/problems/maximum-count-of-positive-integer-and-negative-integer/)
[2300. 咒语和药水的成功对数](https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/) 1477
[2187. 完成旅途的最少时间](https://leetcode.cn/problems/minimum-time-to-complete-trips/) 1641
[2563. 统计公平数对的数目](https://leetcode.cn/problems/count-the-number-of-fair-pairs/) 1721
[275. H 指数 II](https://leetcode.cn/problems/h-index-ii/)
[875. 爱吃香蕉的珂珂](https://leetcode.cn/problems/koko-eating-bananas/) 1766
[2861. 最大合金数](https://leetcode.cn/problems/maximum-number-of-alloys/) 1981
[2517. 礼盒的最大甜蜜度](https://leetcode.cn/problems/maximum-tastiness-of-candy-basket/) 2021
[2439. 最小化数组中的最大值](https://leetcode.cn/problems/minimize-maximum-of-array/) 1965