Given a sorted array of integers, 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].
思路：
我自己用了个最简单的，普通的二分查找，然后两边延伸找起始和结束点。
int *searchRange(int A[], int n, int target) {
int ans[] = {-, -};
int l = , r = n - ;
while(l <= r)
{
int m = (l + r) / ;
if(A[m] == target)
{
ans[] = ans[] = m;
while(ans[] - >= && A[ans[]] == A[ans[] - ]) ans[]--;
while(ans[] + < n && A[ans[]] == A[ans[] + ]) ans[]++;
return ans;
}
else if(A[m] > target)
r = m - ;
else
l = m + ;
}
return ans;
}
大神分成了分别用两次二分查找找起始和结束位置
https://leetcode.com/discuss/18242/clean-iterative-solution-binary-searches-with-explanation中有详细解释
vector<int> searchRange(int A[], int n, int target) {
int i = , j = n - ;
vector<int> ret(, -);
// Search for the left one
while (i < j)
{
int mid = (i + j) /;
if (A[mid] < target) i = mid + ;
else j = mid;
}
if (A[i]!=target) return ret;
else ret[] = i;
// Search for the right one
j = n-; // We don't have to set i to 0 the second time.
while (i < j)
{
int mid = (i + j) / + ; // Make mid biased to the right
if (A[mid] > target) j = mid - ;
else i = mid; // So that this won't make the search range stuck.
}
ret[] = j;
return ret;
}
另一种通过加减0.5来找位置的方法
class Solution:
# @param A, a list of integers
# @param target, an integer to be searched
# @return a list of length 2, [index1, index2]
def searchRange(self, arr, target):
start = self.binary_search(arr, target-0.5)
if arr[start] != target:
return [-1, -1]
arr.append(0)
end = self.binary_search(arr, target+0.5)-1
return [start, end] def binary_search(self, arr, target):
start, end = 0, len(arr)-1
while start < end:
mid = (start+end)//2
if target < arr[mid]:
end = mid
else:
start = mid+1
return start