LeetCode 二分查找法详细解析

二分法总结

• 二分查找模板
  • • 寻找首个不小于目标值的元素
    • 寻找首个大于目标值的元素

  • 严格递增序列

  • • 34. 在已排序数组中定位元素的起始与结束索引

  • 非单调但具有二段性质

  • • 旋转数组相关问题

    • • 33. 在旋转排序数组中进行搜索
      • 81. 在旋转排序数组中进行搜索（进阶版）
      • 153. 确定旋转排序数组中的最小值
    • 162. 寻找数组中的峰值元素

  • 多维数组处理

  • 原木切割问题

二分模板

当条件符合时，应将l设定为mid或者将r设定为mid

找第一个大于等于target的

• 第一种：当条件成立时，r等于mid，此时mid的计算方式为l加r后右移一位。

    while(l<r){

    	int mid = l+r>>1;
    	// 满足条件:找第一个大于等于target的
    	if(nums[mid]>=target){
    		r = mid;
    	}else{
    		l = mid+1;
    	}
    	
    	return r;
    }