首页 > 代码库 > [LeetCode] Search for a Range [34]
[LeetCode] Search for a Range [34]
题目
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]
.
原题链接(点我)
解题思路
查找一个数出现的范围,给一个排好序的数组和一个数,找出这个数在数组中出现的范围。
这个题直接使用一次遍历就可以得到结果,这样的时间复杂度为O(n)。但是对于有序数组我们一般可以使用二分查找可以得到更好的O(logn)的时间复杂度。我们可以使用二分查找找到这个数第一次出现的位置和这个数最后一次出现的位置,这样就可以得到它出现的区间。
代码实现
class Solution { public: vector<int> searchRange(int A[], int n, int target) { vector<int> ret; if(A==NULL || n<=0) return ret; int first = getFirst(A, n, target); int last = getLast(A, n, target); ret.push_back(first); ret.push_back(last); return ret; } int getFirst(int A[], int n, int target){ int begin = 0, end = n-1; int mid; while(begin<=end){ int mid = (begin+end)/2; if(A[mid] == target){ if(mid==0 || A[mid-1]<A[mid]) return mid; else end = mid-1; }else if(A[mid] < target) begin = mid+1; else end = mid-1; } return -1; } int getLast(int A[], int n, int target){ int begin = 0, end = n-1; int mid; while(begin<=end){ int mid = (begin+end)/2; if(A[mid] == target){ if(mid==n-1 || A[mid+1]>A[mid]) return mid; else begin = mid+1; }else if(A[mid] < target) begin = mid+1; else end = mid-1; } return -1; } };
如果你觉得本篇对你有收获,请帮顶。
另外,我开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
另外,我开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
你可以搜索公众号:swalge 或者扫描下方二维码关注我
(转载文章请注明出处: http://blog.csdn.net/swagle/article/details/30466235 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。