问题描述
https://leetcode.com/problems/search-in-rotated-sorted-array/
解决思路
遇到这种排序的，还是首推二分法。这个题里面不管从哪里旋转，一定有一段是升序排列的。分情况讨论：1. 如果mid刚好在有序的里面怎么办？ 2. 如果mid在有序的外面怎么办？具体看代码，走一遍就看懂了
代码
class Solution {
public int search(int[] nums, int target) {
//corner case
if(nums.length == 0 || nums == null) return -1;
int start = 0;
int end = nums.length - 1;
while(start + 1 < end){
int mid = (end - start) / 2 + start;
if(nums[mid] == target) return mid;
//that means the array is ascending
if(nums[start] < nums[mid]){
if(nums[start] <= target && target <= nums[mid]){
end = mid;
}else{
start = mid;
}
}else{//that means the array is not ascending totally and is ascending partly
if(nums[mid] <= target && nums[end] >= target){
start = mid;
}else{
end = mid;
}
}
}
if(nums[start] == target) return start;
if(nums[end] == target) return end;
return -1;
}
}
复杂度分析
- 时间复杂度：log(n)
- 空间复杂度：O(1)
