【二分算法】模板总结
目录
一、二分查找时间复杂度
二、二分查找模板
2.1 模板一：标准的二分查找
2.2 模板二：二分查找左边界
2.3 模板三：二分查找右边界
三、总结：
一、二分查找时间复杂度
时间复杂度可以表示 O(n)=O(log2n)或者O(n)=O(logn)
二、二分查找模板
什么时候可能需要用二分查找？
（1）待查找的数组有序或者部分有序
（2）可以发现二段性
（3）题目要求时间复杂度低于 O(n)，或者直接要求时间复杂度为 O(log n)
2.1 模板一：标准的二分查找
适用场景：数组元素有序且不重复
public int search(int[] nums, int target) {int left = 0,right = nums.length-1;while(left<=right) {int mid = left + ((right-left)>>1);//+运算的优先级高if(target==nums[mid]) return mid;else if(nums[mid]<target) left = mid+1;else right = mid-1;}return -1;}注意点：
（1）为什么 while 循环的条件是 <=，而不是 < ？
当元素只有一个且这个元素正好就是目标值，那么没有=就进入不了循环，得不到正确的结果
（2）计算 mid 时需要防止溢出
left + ((right -left) >> 1)其实和(left + right) / 2是等价的，这样写的目的一个是为了防止(left + right)出现溢出，另外用位运算替代除法提升性能
2.2 模板二：二分查找左边界
public int search(int[] nums, int target) {int left =0,right = nums.length-1;while(left<right) {//1.int mid = left+(right-left)/2;//2.if(nums[mid]<target) left = mid+1;//3.else right = mid;}if(nums[left]==target) return left;return -1;}注意点：
（1）为什么 while 循环的条件是 <，而不是 <= ？
left等于right的时候就已经得到了最终结果，如果判断了，就会进入死循环，因为right后面一直不动
（2） 求中点的操作
求左边界根标准模板一样，不用+1，直接left+（right-left）/2（总个数为偶数个时取中点的时候取左边那个
（3）为啥nums[mid]==target右边界也要变
要寻找左边界，当nums[mid] == target，这个mid的位置不一定就是最左侧的那个边界，所以还要继续收缩右边界
2.3 模板三：二分查找右边界
public int search(int[] nums, int target) {int left =0,right = nums.length-1;while(left<right) {//1.int mid = left+(right-left+1)/2;//2.if(nums[mid]>target) right = mid-1;//3.else left=mid;}if(nums[right]==target) return right;return -1;}注意点：
（1）为什么 while 循环的条件是 <，而不是 <= ？
left等于right的时候就已经得到了最终结果，如果判断了，就会进入死循环，因为right后面一直不动
（2） 求中点的操作
这个和求左边界不一样，需要+1，即left+（right-left+1）/2（总个数为偶数个时取中点的时候取右边那个)，因为如果最后剩两个元素的时候，left一直找左边那个元素，那么将会进入死循环
（3）为啥nums[mid]==target左边界也要变
要寻找右边界，当nums[mid] == target，这个mid的位置不一定就是最右侧的那个边界，所以还要继续收缩左边界
三、总结：
（1）左+1，右不变
找左边界时，left = mid+1；找右边界，left = mid
（2）下面出现-1的时候，上面就要+1
mid-1出现，那么上面求mid就需要+1