Java每日刷题之二分算法

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

 转化 

 通过题目时间复杂度为O(logN),我们就可以联想到二分算法，但是我们前面学到的算法，是查找出，有序数组里的值，并不是求其中的范围，于是我们可以将找到这个值出现的范围转化为 

通过二分法找到最左边下标以及最右边下标

思路：

1.找到最左边下标

第一步：根据mid的与target的大小进行left和right的移动，如图，当t<=mid,说明最小下标点一定在左边，所以移动right ,  将right赋值给mid,重新进入循环，这样即可得到最左边的下标

2.细节处理

1.当right == left的同时，左端点就是这个点，所以循环条件为left < right

2.在mid范围内mid最大值比最小下标小1，所以left = mid+1;

3.当left和right中间无元素时，取中点方式的不同可能会造成死循环，分析图如下

4.得到值最左边下标

具体思路图如下

2.找到最右边下标

 实现思路

细节处理

由于right 在 t < mid内，所以在t < mid内，想要left 与right 相交，就得right = mid -1； 

取中间点的方法和上面找到最左边下标思路相同

注意 

考虑没有target值和数组为空的情况

代码实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] array = {-1,-1};
        if(nums.length == 0) return array;
        //找到左边界点
        int left = 0,right = nums.length-1;
        while(left<right){
            int mid = left +(right-left)/2;
            if(nums[mid] < target){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        if(nums[left] != target) return array;
        else{
            array[0] = left;
        }
        //找到右边界点 
        left = 0;right = nums.length-1;
        while(left<right){
            int mid = left +(right-left+1)/2;
            if(nums[mid] > target){
                right = mid-1;
            }else{
                left = mid;
            }
        }
        if(nums[left] != target) return array;
        else{
            array[1] = right;
        } return array;
    }
   
}