【Hot100】34. 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置
中等题
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。
请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

题解：
在一个范围内，查找一个数字，要求找到这个元素的开始位置和结束位置，这个范围内的数字都是单调递增的，即具有单调性质，因此可以使用二分来做。

两次二分，第一次二分查找第一个t>=target的位置，第二次二分查找最后一个t<=target的位置。
查找成功则返回两个位置下标，否则返回[-1,-1]。

• 模板一：当我们将区间[l, r]划分成[l,mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1，计算mid时不需要加1，即mid=(l+r)/2。
• 模板二：当我们将区间[l, r]划分成[l,mid−1]和[mid,r]时，其更新操作是r=mid−1或者l=mid，此时为了防止死循环，计算mid时需要加1，即mid=(l+r+1)/2。

注意：
当左边界要更新为l = mid时，就令 mid =(l + r + 1)/2，相当于上取整，此时就不会因为r取特殊值 r = l + 1而陷入死循环了。

class Solution {
    
    public int[] searchRange(int[] nums, int target) {
    
        if(nums.length == 0) {
    
            return new int[]{
    -1,-1};
        }
    
        int l = 0, r = nums.length - 1; //二分范围
        while( l < r)			        //查找元素的开始位置
        {
    
            int mid = (l + r )/2;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if( nums[r] != target) {
    
            return new int[]{
    -1,-1}; //查找失败
        }
        int L = r;
        l = 0; 
        r = nums.length - 1;     //二分范围
        while( l < r)			        //查找元素的结束位置
        {
    
            int mid = (l + r + 1)/2;
            if(nums[mid] <= target ) l = mid;
            else r = mid - 1;
        }
        return new int[]{
    L,r};
    }
}

class Solution {
    
    public int[] searchRange(int[] nums, int target) {
    

        if(nums.length == 0){
    
            return new int[]{
    -1,-1};
        } 

        int l = 0, r = nums.length - 1; //二分范围 左闭右闭
        
        //查找元素的开始位置
        while( l < r){
    
            int mid = (l + r )/2;
            if(nums[mid] >= target){
    
                r = mid;
            } else{
    
                l = mid + 1; 
            }                    
        }

        if( nums[r] != target){
    
            return new int[]{
    -1,-1}; //查找失败
        } 
        
        int L = r;
        l = 0; r = nums.length - 1;     //二分范围

        //查找元素的结束位置
        while( l < r)			        
        {
    
            int mid = (l + r + 1)/2; //注意
            if(nums[mid] <= target ){
    
                l = mid;
            } else {
    
                r = mid - 1;
            }
        }
        return new int[]{
    L,r};
    }
}