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].
题目大意：
给定按升序排序的整数数组，找到给定目标值的开始和结束位置。您的算法的运行时复杂度必须按照O（log n）的顺序。如果在数组中找不到目标，则返回[-1，-1]。例如，给定[5，7，7，8，8，10]和目标值8，返回[3，4]。
题目分析：
注意到题目要求时间复杂度为O （log n），可以采用二分法进行目标值搜索。当搜索到目标值时，对中位数进行加一或减一操作确定另一目标数位置。
代码如下：
- Java
int[] result = {-1,-1};
int left = 0;
int right = nums.length-1;
while (left <= right) {
int mid = (right+left)/2;
if (nums[mid] > target)
right = mid-1;
else if (nums[mid] < target)
left = mid+1;
else {
result[0] = mid;
result[1] = mid;
int i = mid-1;
while (i>=0 && nums[i] == target) {
result[0] = i;
--i;
}
i = mid+1;
while (i<nums.length && nums[i] == target) {
result[1] = i;
++i;
}
break;
}
}
return result;
- Python
left = 0
right = len(nums)-1
result = [-1,-1]
while left<=right:
mid = (left + right) / 2
if nums[mid] > target:
right = mid-1
elif nums[mid] < target:
left = mid+1
else:
result[0] = mid
result[1] = mid
i = mid-1
while i>=0 and nums[i] == target:
result[0] = i
i-=1
i = mid+1
while i<len(nums) and nums[i] == target:
result[1] = i
i+=1
break
return result
