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
return [5, 7, 7, 8, 8, 10]
and target value 8,[3, 4]
.思路:
既然要求O(log n)那必然又是binary search变种。要找到target在数组中的左右边界,必然先得要在数组中找到一个target。一种条件反射的思路是binary search找到target,即A[mid] = target,然后从mid开始向左右扫描来发现左右边界。但显然这种算法不是O(log n)的,比如当所有元素都一样,并且等于target时,算法退化为O(n)。
所以这里当A[mid] = target时,我们必须继续用二分法来查找左右边界。以下面数组为例:
4 5 8 8 8 8 9 9 10
target = A[mid=4] = 8
此时要在A[0:3]中寻找left,在A[5:8]中寻找right。
搜索left:
4 5 8 8
target != A[mid],搜索 A[mid+1 : end]。
8 8
target = A[mid],搜索A[start: mid-1]
start > end,left = start
搜索right:
8 9 9 10
target != A[mid],搜索A[start : mid-1]。
8
target = A[mid],搜索A[mid+1 : end]。
start > end,right = end
总结的规律就是:
二分查找时特殊处理target = A[mid]的情况
对搜索left:如果target = A[mid]则继续向左找,否则向右找。直到搜索结束,left = start
对搜索right:如果target = A[mid]则继续向右找,否则向左找。直到搜索结束,right = end
最后判断如果A[left], A[right] != target,则表明target不存在于数组中, left = right = -1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | class Solution { public: vector<int> searchRange(int A[], int n, int target) { vector<int> range; range.push_back(findLeftMost(A, n, target)); range.push_back(findRightMost(A, n, target)); return range; } int findLeftMost(int A[], int n, int target) { int start = 0, end = n-1; while(start<=end) { int mid = start + (end-start)/2; if(target<A[mid]) end = mid-1; else if(target>A[mid]) start = mid+1; else end = mid-1; } if(start>=0 && start<n && A[start]==target) return start; return -1; } int findRightMost(int A[], int n, int target) { int start = 0, end = n-1; while(start<=end) { int mid = start + (end-start)/2; if(target<A[mid]) end = mid-1; else if(target>A[mid]) start = mid+1; else start = mid+1; } if(end>=0 && end<n && A[end]==target) return end; return -1; } }; |
This comment has been removed by the author.
ReplyDelete这个算法worst case 也是o(n)吧
ReplyDeletefindLeftMost和findRightMost可以合并成一个循环,当找到target的第一次出现的位置mid的时候,令left = mid,right = A.size()-1,继续循环即可。
ReplyDeleteif (nums[mid] == target)
Delete{
// If we haven't find the first appearance of target, and current is not the first appearance of target
// keep going left.
if (result.empty() && (mid > 0 && nums[mid - 1] == target)) // go left to find the first target
{
right = mid - 1;
}
else if (!result.empty() && (mid < nums.size() -1 && nums[mid + 1] == target)) // If we have found the first apperance of target, go right to find the last appearance of target
{
left = mid + 1;
}
else
{
result.push_back(mid);
if (result.size() == 1)
{
// So now nums[mid] is the first appearance of target, now we need to find the last appearance of target.
// rest left = mid + 1 and right to end of nums,
left = mid;
right = nums.size() - 1;
}
else
{
break;
}
}
}