二分法求左右边界

二分法求左右边界搞定

鉴于本人每次做二分的题都被二分的边界搞的云里雾里的，所以这次直接一劳永逸。道理我都懂，就是之前不想整理。

直接定义left和right为左闭右闭，这个很重要。当然二分也要求数组必须是有序的

比如：数组长度为10，则left=0；right=9；即左右两个数都可以取到。

因此我们的代码可以写为：

while(left<=right){
    int mid=left+(right-left)/2;//中点
    //条件判断
    //如果要找的是确定值那么很简单
     if(nums[mid]==target) return;
     if(nums[mid]>target) right=mid-1;
     if(nums[mid]<target) left=mid+1;
}

难点当然不是这个，难的是哪种找左右边界的题。如：找到大于等于target 的第一个数，即右边界。

while(left<=right){
    int mid=left+(right-left)/2;//中点
    //条件判断
  if(nums[mid]<=target) left=mid+1;
  if(nums[mid]>target) right=mid-1;
}
//注意一下越界问题,即left>=length
if (right < 0 || nums[right] != target) {
			return -1;
	}
return right;

找到小于等于target的第一个数,即左边界

while(left<=right){
    int mid=left+(right-left)/2;//中点
    //条件判断
  if(nums[mid]<target) right=mid-1;
  if(nums[mid]>=target) left=mid+1;
}
//注意一下越界问题,即right<0
if (left >= len || nums[left] != target) {
			left= -1;
		}
return left;

又如找大于target的第一个数

while(left<=right){
    int mid=left+(right-left)/2;//中点
    //条件判断
  if(nums[mid]<target) left=mid+1;
  if(nums[mid]>target) right=mid-1;
  if(nums[mid]==target) ans=mid; right=mid-1;
}