首页 > 代码库 > 搜索区间
搜索区间
搜索区间
给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中,则返回[-1, -1]
样例
给出[5, 7, 7, 8, 8, 10]
和目标值target=8
,
返回[3, 4]
挑战
时间复杂度 O(log n)
标签
数组 排序数组 二分法
1 class Solution { 2 /** 3 *@param A : an integer sorted array 4 *@param target : an integer to be inserted 5 *return : a list of length 2, [index1, index2] 6 */ 7 public: 8 vector<int> searchRange(vector<int> &A, int target) { 9 // write your code here 10 vector<int> result; 11 int size = A.size()-1; 12 if(A.empty()) { 13 result.push_back(-1); 14 result.push_back(-1); 15 } 16 else { 17 result.push_back(getFirstTarget(A, target, 0, size)); 18 result.push_back(getLastTarget(A, target, 0, size)); 19 } 20 return result; 21 } 22 23 int getFirstTarget(vector<int> &A, int target, int low, int high) { 24 if(low > high) 25 return -1; 26 int mid = (low+high)/2; 27 if(A[mid] == target) { 28 if((mid>0 && A[mid-1]!=target) || mid==0) 29 return mid; 30 else 31 high = mid-1; 32 } 33 else if(A[mid] > target) 34 high = mid-1; 35 else 36 low = mid+1; 37 38 return getFirstTarget(A, target, low, high); 39 } 40 41 int getLastTarget(vector<int> &A, int target, int low, int high) { 42 int size = A.size()-1; 43 if(low > high) 44 return -1; 45 int mid = (low+high)/2; 46 if(A[mid] == target) { 47 if((mid<size && A[mid+1]!=target) || mid==size) 48 return mid; 49 else 50 low = mid+1; 51 } 52 else if(A[mid] > target) 53 high = mid-1; 54 else 55 low = mid+1; 56 57 return getLastTarget(A, target, low, high); 58 } 59 };
搜索区间
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。