Given an array of integers nums sorted in ascending order, 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].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Solution
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums==null) return null;
return bs(nums,target);
}
private int[] bs(int[] nums,int t){
int n=nums.length;
int s=-1,e=-1;
int l=0,r=n-1;
while(l<=r){
int m=l+(r-l)/2;
if(t<nums[m]){
r=m-1;
}else if(t>nums[m]){
l=m+1;
}else{
s=m;
e=m;
int tmp=bsRange(nums,t,l,m-1,true);
s=tmp<0?s:tmp;
tmp=bsRange(nums,t,m+1,r,false);
e=tmp<0?e:tmp;
return new int[]{s,e};
}
}
return new int[]{s,e};
}
private int bsRange(int[] nums,int t,int l,int r,boolean f){
int idx=-1;
while(l<=r){
int m=l+(r-l)/2;
if(t<nums[m]){
r=m-1;
}else if(t>nums[m]){
l=m+1;
}else{
idx=m;
if(f){
r=m-1;
}else{
l=m+1;
}
}
}
return idx;
}
}
时间O(logn)
空间O(1)
既然要求logn时间那得是二分查找了,我的思路是先用二分法找到他在不在,在的话将他作为分割点,分成两个子数组,对这两个子数组进行二分查找,在找到等于时不返回,继续遍历直到结束,使用idx记录最后一个匹配的位置。令我没想到的是竟然打败了100%的人。标准答案是用一个方法查找左右,我个人理解先查在不在应该是可以剪枝的。
网友评论