方法1：
1.思路：旋转数组的特点是从数组中的元素分两部分，[0, k], [k+1, n]都递增，且nums[k] > nums[k+1].所以只需要找到k的位置，分别对两部分二分查找即可。
2.代码：
class Solution {
public int search(int[] nums, int target) {
//k指向旋转数组前半段的最后一个元素
int k = -1;
int n = nums.length - 1;
//ans返回结果
int ans = -1;
//寻找k，k的特点是k的元素大于k+1
for(int i = 0 ; i < nums.length - 1; i++){
if(nums[i] > nums[i+1]){
k = i;
break;
}
}
//如果左半部分找到了target
if(binSearch(nums, 0, k, target) >= 0){
ans = binSearch(nums, 0, k, target);
}
//如果右半部分找到了target
if(binSearch(nums, k+1, n, target) >= 0){
ans = binSearch(nums, k+1, n, target);
}
return ans;
}
int binSearch(int[] num, int l, int r, int target){
while (l <= r){
int mid = l + (r - l) / 2;
if(num[mid] == target){
return mid;
}else if(num[mid] < target){
l = mid + 1;
}else {
r = mid - 1;
}
}
return -1;
}
}
3.复杂度分析：时间0(n),需要遍历数组找到k.空间0(1)
方法2：直接用二分查找。
1.思路：旋转数组分为两部分，如果nums[mid] > nums[0]，则说明0到mid是有序的。这时候只需要判断target是否在left到mid区间即可.反之mid落在了右半部，则判断target是否在右边部分即可，target > nums[mid]&& target <=nums[right]。
2.代码：
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1;
if(n == 0)return -1;
if(n == 0)return nums[0] == target ? 0 : -1;
while (left <= right){
int mid = left + (right - left ) / 2;
if(nums[mid] == target){
return mid;
}
//[+++++---],左右两部分均递增。
// |(|代表mid)
//如果nums[mid] > nums[0] ,说明前面一直到mid都为递增有序
//>=是因为可能只有两个元素[3, 1]target = 1,mid = nums[0]
if(nums[mid] >= nums[0]){
//如果target介于0和mid之间
if(target >= nums[0] && target < nums[mid]){
right = mid - 1;
}else {
left = mid + 1;
}
//mid落在了右半区
}else {
if(target > nums[mid] && target <= nums[right]){
left = mid + 1;
}else {
right = mid - 1;
}
}
}
return -1;
}
}
3.复杂度分析：时间0(log(n))空间0(1).
