大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
问题叙述性说明:
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 ofO(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]
.
基本思路:
此题能够用二分查找法解决。
假设数组中没有target,能够在O(lgn)时间完毕。
假设数组中有target,当发现target后,对前后的内容继续用二分法 查找这种位置pos 。
- 前面的pos须要满足 A[pos] < target && A[pos+1] == target. pos+1即是開始位置。
- 后面的pos须要满足 A[pos] > target && A[pos-1] == target . pos-1是结束位置。
代码:
vector<int> searchRange(int A[], int n, int target) { //C++ vector<int> result(2); int low = 0, high = n-1; int mid, begin = -1, end = -1; while(low <= high) { mid = (low+high)/2; if(A[mid] > target) high = mid - 1; else if(A[mid] < target) low = mid + 1; else { begin = mid; end = mid; //get begin if(low <= begin -1){ while((low <= begin-1) && !(A[low]<target && A[low+1] == target) ) { mid = (low + begin-1)/2; if(A[mid] < target) low = mid+1; else begin = mid; } if(A[low]<target && A[low+1] == target) begin = low+1; } //get end if(high >= end+1){ while((high >= end+1) &&!(A[high]>target && A[high-1] == target)) { mid = (high + end +1)/2; if(A[mid] > target) high = mid - 1; else end = mid; } if(A[high]>target && A[high-1] == target) end = high - 1; } break; } } result[0] = begin; result[1] = end; return result; }
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116862.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...