题目
讲解
题干和提示中一共给出了两个很重要的信息,一个是未旋转之前,数组是有序数组;第二个是nums中的每个值都独一无二;并且最后说明了时间复杂度为O(log n),看到log,先想到二分
- 还是万年不变的y总二分模板
我们从这两条信息可以想到,如果用二分法去分割这个数组,则肯定是一个区间为有序,另一个区间为无序;
然后看一下这个有序的区间,target可以通过对左右两边界的对比,得知这个数是否在有序区间里,如果在,则对这个有序区间进行二分,如果不是,则target肯定是在无序区间,在无序区间中二分也是一个道理,肯定回出现一个有序一个无序,然后继续判断即可,最终得出结果。
题解
public int search(int[] nums, int target) {
int l = 0, r = nums.length-1;
while(l < r){
int mid = (l+r)/2;
// 即左分区有序
if(nums[l] < nums[mid]){
//即target在左区间出现
if(nums[l]<=target && nums[mid]>=target){
r = mid;
}else{
l = mid+1;
}
}else{ //即右分区有序
//即target在右区间出现
if(nums[mid+1]<=target && nums[r]>=target){
l = mid+1;
}else{
r = mid;
}
}
}
if(nums[l] == target){
return l;
}else{
return -1;
}
}