二分查找及左边界和右边界查找

二分查找

对于二分查找而言，其定义这里就不展开说了，这里主要是给出代码，并且说明几个容易搞错的地方，代码如下：

public int binary_search(int[] nums,int target){
    int left = 0, right = nums.length - 1;
    int mid = 0;
    while(left<=right){
        mid = left + (right - left) /2; // 等同于(left+ right) /2 只是可以避免溢出
        if(nums[mid]< target){
            left = mid + 1;
        }else if(nums[mid]>target){
            right = mid - 1;
        }else{ // nums[mid] == target
            return mid;
        }
    }
    return left;// 插入位置
}

有几个关键地方，第一个是while里面注意是<=, 如果是<的话，到最后可能会少一个left==right的情况时对应的mid。

另外就是mid = left + (right - left) /2 可以避免加法产生的溢出，因为left和right可能都很大，直接加会溢出，先相减再加就可以避免溢出。

最后是return left，这个left就是对应如果没有找到的话，我们的插入位置，比如{1,3,4} 查找2没有，则插入位置是1。

二分查找的左边界问题

左边界问题，就是找出对应值的最左边的那个，比如{2,8,8}中8的左边界就是1,这里我给出两种解法，第一种和上面的二分查找格式统一，只有一点区别，另外一个在格式上有很大不同，根据自己情况食用。

左边界一

int left_bound(int[]nums,int target){
    int left = 0,right = nums.length-1,mid=0;
    while(left<=right){
        mid = left +(right-left)/2;
        if(nums[mid]==target){
            right = mid-1;
        }else if(nums[mid]<target){
            left = mid+1;
        }else if(nums[mid]>target){
            right = mid -1;
        }
    }
    // 如果搜索的数字比所有的都大，最终right位置在最后一个元素，left = right+1
    //             比所有的都小，最终left 在0 。所以如果left>=nums.length || nums[left]!=target则未找到
    if(left>=nums.length || nums[left]!=target){
        return -1;
    }
    return left;
    
}

这里也有几个要注意的地方，第一个是关于==的时候数值的更新，对于之前的二分查找，如果==的话，直接return即可，但是这里因为我们需要左边界，所以要向左边逼近，所以这里的赋值只可能是right = mid 或者right = mid-1，因为这样才能向左逼近。但对于right = mid来说可能出现死循环，因为while的条件是<= ,比如当前left = 3， right = 4，那么mid = 3，更新rihgt = 3，然后满足while，并且mid = 3，更新right = 3，发现死循环了，所以只能利用right = mid -1，这样最后跳出循环的时候right的位置是左边界-1，而left可以当作左边界。

第二个注意的是，在返回之前进行一下边界判断。

左边界二

这个结构就和之前的不统一了，先看代码:

public int left_bound(int[] nums ,int target){
    if(nums.length==0){
        return -1;
    }
    int left = 0 ,right = nums.length - 1;
    int mid = 0;
    while(left< right){
        mid = left + (right - left) /2;
        if(nums[mid]>target){
            right = mid - 1;
        }else if(nums[mid]<target){
            left = mid + 1;
        }else{
            right = mid; // 等于的时候说明左边界在[left,mid] 所以right 只能缩小到mid ，而因此外层循环要用<
        }
    }
    // left也是最后的插入位置
    return left;
}

可以看出，这里的while中的判断条件是left < right。 而对于==的时候的也变为了right = mid，这是因为当等于的时候其实左边界范围在[left,mid]，所以right应该更新为mid，但是如果这样，之前说过，可能会出现死循环，所以这里的while循环就要对应改为< ,而不能用<=。

二分查找的右边界问题

右边界一

int right_bound(int[] nums,int target){
    int left = 0,right = nums.length-1,mid = 0;
    while(left<=right){
        mid = left +(right-left)/2;
        if(nums[mid]==target){
            left = mid+1;
        }else if(nums[mid]<target){
            left = mid +1;
        }else if(nums[mid]>target){
            right = mid -1;
        }
    }
    if(right<0 || nums[right]!=target){
        return -1;
    }
    return right;
}

这种方式和二分查找统一，主要注意点就是在等于的时候，因为我们要找右边界，所以将left向右边逼近，同样这里有一个问题是left不能赋值为mid，因为会造成死循环。这样left就相当于在右边界+1的位置，而right相当于右边界。最后同样对right进行一下判断避免越界。

右边界二

public int right_bound(int[] nums ,int target){
    if(nums.length==0){
        return -1;
    }
    int left = 0 ,right = nums.length - 1;
    int mid = 0;
    while(left< right){
        mid = left + (right - left + 1) /2; // +1 其实是上取整，避免最后left 和right对应值相等且等于target，这样mid还是等于left，然后判断赋值left = mid ，这样就死循环了
        if(nums[mid]>target){
            right = mid - 1;
        }else if(nums[mid]<target){
            left = mid + 1;
        }else{
            left = mid; // 等于的时候说明左边界在[mid,right] 所以left 只能缩小到mid ，而因此外层循环要用<
        }
    }
    return left;
}

这里主要注意的是，mid的计算是向上取整，因为如果和以前一样，那么如果left=3，right =4，且都是target，那么首先mid = 3，然后更新left = 3，发现while死循环，因为我们要找右边界，所以可以将mid计算的时候上取整即可。

本文地址：https://blog.csdn.net/qq_28888837/article/details/107517311