Given an array of integers 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].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

一刷
题解：要使用两次binary search来分别搜索target值的最左端和最右端。最后需要判断一下求出来的left 是否<= right，否则 如果有没有找到的情况indices会是0（初始的left或right）而不是-1

public class Solution {
    public int[] searchRange(int[] nums, int target) {
       int[] res = {-1, -1};
       if(nums == null || nums.length ==0) return res;
       int lo = 0, hi = nums.length-1;
       while(lo <= hi){
           int mid = lo + (hi - lo)/2;
           if(target > nums[mid]) lo = mid+1;
           else hi = mid-1;
       }
       
       int left = lo;
       lo = 0;
       hi = nums.length - 1;
        while(lo <= hi){
           int mid = lo + (hi - lo)/2;
           if(target >= nums[mid]) lo = mid+1;
           else hi = mid-1;
       }
       
      int right = hi;
      if(left<=right){
          res[0] = left;
          res[1] = right;
      }
       
       return res;
    }
}

二刷
思路同上。同时要注意，寻找左半边，当target <= nums[mid] hi = mid;(来保持这个值），如果找到，low会不断减少。右边同理。

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int lo = 0, hi = nums.length-1;
        int[] res = new int[2];
        res[0] = -1;
        res[1] = -1;
        if(nums.length == 0) return res;
        
        //search for the left one
       while(lo<hi){
           int mid = lo + (hi-lo)/2;
           if(nums[mid]<target) lo = mid+1;
           else hi = mid;
       }
        
        if(nums[lo]!=target) return res;
        else res[0] = lo;
        
        //search for the right one
        hi = nums.length-1;
        while(lo<hi){
            int mid = lo + (hi-lo)/2 + 1;
            if(nums[mid]>target) hi = mid-1;
            else lo = mid;
        }
        res[1] = hi;
        return res;
    }
}

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = searchLeft(nums, target);
        if(nums[left]!=target) return new int[2];
        int right = searchRight(nums, target, left);
        if(left == right) return new int[]{left};
        else return new int[]{left, right};
    }
    
    private int searchLeft(int[] nums, int target){
        int lo = 0, hi = nums.length-1;
        while(lo<hi){
            int mid = lo + (hi-lo)/2;
            if(nums[mid] == target) hi = mid;
            else lo = mid+1;
        }
        return lo;
    }
    
    private int searchRight(int[] nums, int target, int from){
        int lo = from, hi = nums.length-1;
        while(lo<hi){
            int mid = lo + (hi-lo)/2 + 1;
            if(nums[mid]>target) hi = mid-1;
            else lo = mid;
        }
        return hi;
    }
}