Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

1.思路

首先，这道题需要找一个数组中某个数的最大、最小索引。自然而然就是遍历，然而时间复杂度规定了O(log n)。那么就想到了二分查找。

2.代码实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
      int left = findRange(nums,target,true);
       if(left == -1){
         return new int[]{-1,-1};
       }
      int right = findRange(nums,target,false);
      return new int[]{left,right};
    }

   /**
    * left:true为找左边界，false找右边界
    */
    public int findRange(int[] nums, int target,boolean left){
        int len = nums.length;
        int low = 0;
        int high = nums.length - 1;
        while(low<=high){
            int mid = low + ((high-low)>>1);
            if(nums[mid]>target){//①
                high = mid-1;
            }else if(nums[mid]<target){//②
                low = mid+1;
            }else{//③
                if(left && (mid==0 || nums[mid-1]!=target)){//找到左边界
                   return mid;
                }else if(!left && (mid==(len-1)||nums[mid+1]!=target)){//找到右边界
                    return mid;
                }else{//④
                    if(left){
                        high = mid-1;//不是第一个数，继续往左边递归
                    }else{
                        low = mid+1;//不是最后一个数，继续往右边递归
                    }
                }
            }
        }
        return -1;
    }
}

第①、②步和正常二分查找一样，区别在于第③、④步。
运行时间快于100%。

再改进一下：

class Solution {
    public int[] searchRange(int[] nums, int target) {
      int left = findFirst(nums,target);//找到左边界索引
       if(left == -1){
         return new int[]{-1,-1};
       }
       int right = left;
       for(int i = left;i<nums.length;i++){//直接通过for循环遍历取得右边界索引
           if(nums[i]>target){
               break;
           }
           right = i;
       }
      return new int[]{left,right};
    }
    
    public int findFirst(int[] nums, int target){
        int len = nums.length;
        int low = 0;
        int high = nums.length - 1;
        while(low<=high){
            int mid = low + ((high-low)>>1);
            if(nums[mid]>target){
                high = mid-1;
            }else if(nums[mid]<target){
                low = mid+1;
            }else{
                if(mid==0 || nums[mid-1]!=target){
                   return mid;
                }else{
                    high = mid-1;
                }
            }
        }
        return -1;
    }
}