题目
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)
分析
可以用两次二分查找，先找到最左边的值，再找到最右边的值。
找最左边值的时候
- If A[mid] < target, then the range must begins on the right of mid (hence i = mid+1 for the next iteration)
- If A[mid] > target, it means the range must begins on the left of mid (j = mid-1)
- 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};
}
