首页 > 代码库 > LeetCode-Search for a Range
LeetCode-Search for a Range
<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">Given a sorted array of integers, find the starting and ending position of a given target value</span>
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自己的编译器会报错。
int a,b; a=num; b=num;
while(A[a] == target ) a--; while(A[b] == target ) b++;最开始的时候,代码是这样的,对二分搜索找到了target,再进行往前往后的找。在codeblocks上运行是无错, 但就是提交在LeetCode上面会出现问题。
最后做了一个数组的溢出判断,终于AC了
int a,b; a=num; b=num; while(A[a] == target && a >= 0) a--; while(A[b] == target && b <= n-1) b++;
class Solution { private: int binary_search(int* a, int len, int goal) { int low = 0; int high = len - 1; while(low <= high) { int middle = (low + high)/2; if(a[middle] == goal) return middle; else if(a[middle] > goal) high = middle - 1; else low = middle + 1; } return -1; } public: vector<int> searchRange(int A[], int n, int target) { vector<int> s; int num = binary_search(A,n,target); if(num == -1) {s.push_back(-1);s.push_back(-1);} else { int a,b; a=num; b=num; while(A[a] == target && a >= 0) a--; while(A[b] == target && b <= n-1) b++; s.push_back((++a)); s.push_back((--b)); } return s; } };
LeetCode-Search for a Range
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。