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].
題目大意：
給定按升序排序的整數(shù)數(shù)組搪柑，找到給定目標(biāo)值的開始和結(jié)束位置亏拉。您的算法的運(yùn)行時(shí)復(fù)雜度必須按照O（log n）的順序。如果在數(shù)組中找不到目標(biāo)，則返回[-1火惊，-1]狼钮。例如卧抗，給定[5读跷，7，7蠢络，8衰猛，8，10]和目標(biāo)值8刹孔，返回[3啡省，4]。
題目分析：
注意到題目要求時(shí)間復(fù)雜度為O （log n）芦疏，可以采用二分法進(jìn)行目標(biāo)值搜索冕杠。當(dāng)搜索到目標(biāo)值時(shí)，對(duì)中位數(shù)進(jìn)行加一或減一操作確定另一目標(biāo)數(shù)位置酸茴。
代碼如下：
- 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
