二分查找法

1、思路
(二分) O(logn)O(logn)

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

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

2、java代码

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};
    }
}