首页 > 代码库 > [leetcode] Search for a Range
[leetcode] Search for a Range
Search for a Range
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].
思路：
以leetcode的风格，这个题目遍历数组是不可能通过的，给的题目分类果然是二分查找的。很容易想到，可以通过二分查找找到目标值，然后在找到值的下标左右分别顺序寻找边界。这样做还是超时了，因为算法在1 1 1 1 1这种会退化成O(n)的复杂度。
为了避免超时，那只能在找到后继续二分查找了。再进行二分查找时，主要是判断beg,end和mid的关系。我也是一点一点提交试出来的，没有一次性全部考虑到。
题解：
class Solution {public: int beg = -1; int end = -1; void find(int a[], int l, int r, int target) { if(l<=r) { int mid = (l+r)/2; if(a[mid]==target) { if(beg==-1 || mid<beg) beg = mid; if(end<mid) end = mid; find(a, l, mid-1, target); find(a, mid+1, r, target); } else if(a[mid]<target) find(a, mid+1, r, target); else find(a, l, mid-1, target); } } vector<int> searchRange(int A[], int n, int target) { vector<int> res; find(A, 0, n-1, target); res.push_back(beg); res.push_back(end); return res; }};
[leetcode] Search for a Range
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。