首页 > 代码库 > Leetcode Search for a Range
Leetcode 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].
二分查找
第一步找到元素的起点
第二步找到元素的终点
class Solution {public: int lower_bound(int A[], int n, int target){ int left = 0, right = n-1; while(left < right){ int mid = (left+right)/2; if(A[mid] < target) left = mid+1; else right = mid; } if(A[left]!=target) return -1; else return left; } int upper_bound(int A[], int n, int target){ int left = 0, right = n-1; while(left <= right){ int mid = (left+right)/2; if(A[mid] > target) right = mid-1; else left = mid+1; } if(A[right]!=target) return -1; else return right; } vector<int> searchRange(int A[], int n, int target) { vector<int> res; res.push_back(lower_bound(A,n,target)); res.push_back(upper_bound(A,n,target)); return res; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。