题目

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].

给定一个可能包含重复数字已排过序的数组和一个目标值，在数组中找到目标值第一次出现和最后一次出现的位置，如果没有则返回{-1,-1}，要求时间复杂度为O(logn)

分析

可以用两次二分查找，先找到最左边的值，再找到最右边的值。
找最左边值的时候

1. If A[mid] < target, then the range must begins on the right of mid (hence i = mid+1 for the next iteration)
2. If A[mid] > target, it means the range must begins on the left of mid (j = mid-1)
3. If A[mid] = target, then the range must begins on the left of or at mid (j= mid)
   可以把2 3 融合到一个条件，设置 j = mid

找最右边值的一边需要做一些变化，如果设置mid = (i + j)/2会在找到一个相等的数时停滞不前， 因为除法会偏向小的那边，可以令 mid = (i + j + 1)/2，使其偏向右边。

代码

public int[] searchRange(int[] nums, int target) {
    if(nums == null || nums.length == 0) return new int[]{-1, -1};  //边界检查不可少
    //找最左边相等的
    int i = 0, j = nums.length - 1;
    while(i < j){
        int mid = (i + j) / 2;
        if(nums[mid] < target){
            i = mid + 1;
        }else{
            j = mid;
        }
    }
    if(nums[i] != target){
        return new int[]{-1, -1};
    }
    int left = i;
    j = nums.length - 1;
    #找最右边相等的，从已知的相等的最左边的位置开始
    while(i < j){
        int mid = (i + j + 1)/2;
        if(nums[mid] > target){
            j = mid - 1;
        }else{
            i = mid;
        }
    }
    return new int[]{left, i};
}