34. 在排序数组中查找元素的第一个和最后一个位置 (opens new window)

1.二分查找

分析：用二分的必要条件就是答案出现在的位置，只能在左边界或者是右边界。从而缩小下一次的搜索范围。

先通过二分找到任意一个target的索引mid，接着划分为两个区间【0,mid】和【mid,nums.length-1】分别进行二分,左区间找到target的左边界，右区间找到target的右边界。只要不等于target就缩小边界。

class Solution {
    int[] res;
    public int[] searchRange(int[] nums, int target) {
        res=new int[2];
        res[0]=-1;
        res[1]=-1;
        if(nums.length==1){
            if(nums[0]==target){
                res[0]=0;
                res[1]=0;
            }
            return res;
        }
        int start=0,end=nums.length-1;
        while(start<end){
            int mid=(start+end)/2;
            if(nums[mid]>target){
                end=mid-1;
                //防止单个元素情况
                if(start==end&&nums[start]==target){
                    res[0]=start;
                    res[1]=start; 
                }
            }
            else if(nums[mid]<target){
                start=mid+1;
                if(start==end&&nums[start]==target){
                    res[0]=start;
                    res[1]=start; 
                }
            }
            else{
                //左半段二分找出target左边界
                int lright=mid,rleft=mid;
                while(start<lright){
                    int midleft=(start+lright)/2;
                    if(nums[midleft]!=target) start=midleft+1;
                    else lright=midleft;
                }
                //右半段二分找出target右边界
                while(rleft<end){
                    int midleft=(rleft+end)/2;
                    if(nums[midleft]!=target) end=midleft-1;
                    else{
                        rleft=midleft;
                        if(rleft+1==end){
                            if(nums[end]==target) rleft=end;
                            break;
                        }
                    }
                }
                res[0]=lright;
                res[1]=rleft;
                break;
            }
        }
        return res;
    }
}

2.优化

另一种二分的思路，直接对全局进行二分，每一轮搜索时不需要找到target的左右边界，找到【左边界-1】和【右边界+1】这两个位置同样可以确定target的左右边界。

也就是说第一轮通过二分找到小于target的最大值。第二轮找到大于target的最小值。