### 题目

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

0 1 2 4 5 6 7 -> 4 5 6 7 0 1 2

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

### 单指针遍历 $O(n)$

1. 数组越界要循环回到另一个端点。
2. 每次都需要检测pivot点。越过pivot点，结束程序。

#### 代码

public class Solution {
public int search(int[] nums, int target) {
if (nums.length == 0) { return -1; }
if (nums.length == 1) { return (target == nums[0])? 0 : -1; }
int cursor = 0, next = 0;
while (true) {
if (nums[cursor] == target) { return cursor; }
if (nums[cursor] < target) {
next = (cursor + 1) % nums.length;
if (nums[next] < nums[cursor] || nums[next] > target) { return -1; }
}
if (nums[cursor] > target) {
next = (cursor - 1 < 0)? cursor - 1 + nums.length : cursor - 1;
if (nums[next] > nums[cursor] || nums[next] < target) { return -1; }
}
cursor = next;
}
}
}

### Binary Search $O(\log_{}{n})$

1. 用Binary Search找到那个pivot点，就是最小的那个数字。
2. pivot看做是当前数组在标准数组上的一个偏移值。做一个在标准数组上做一个Binary Search。

2是最小的数字。
[10,12,>2<,4,6,8]

[2,4,6,8,10,12]  // 标准数组

#### 代码

public class Solution {
public int search(int[] nums, int target) {
if (nums.length == 0) { return -1; }
if (nums.length == 1) { return (target == nums[0])? 0 : -1; }
int pivot = pivot(nums,0,nums.length-1);
return searchRecur(nums,0,nums.length-1,target,pivot);
}
public int pivot(int[] nums, int low, int high) { // 找最小数(转动的那个点)
if (high == low) { return low; }
int median = low + (high - low) / 2;
if (nums[median] < nums[high]) {
return pivot(nums,low,median);
} else {
return pivot(nums,median+1,high);
}
}
public int searchRecur(int[] nums, int low, int high, int target, int rotate) { //正常的二分查找
if (low > high) { return -1; }
int median = low + (high - low) / 2;
int medianRotated = (median + rotate) % nums.length; // 根据偏移值找到点在数组上的实际位置
if (nums[medianRotated] < target) {
return searchRecur(nums,median+1,high,target,rotate);
} else if (nums[medianRotated] > target) {
return searchRecur(nums,low,median-1,target,rotate);
} else {
return medianRotated;
}
}
}

### 也可以直接在数组上二分查找 $O(\log_{}{n})$

1. 如果像[7,0,1,3,5,6]这样，nums[mid] < nums[hi]，说明右半边1,3,5,6是升序的。
• 如果1 < target <= 6，说明目标在3,5,6里能找到，所以放弃左半边7,0,1
• 否则，说明目标不在1,3,5,6，只需要到7,0,1里找。
2. 如果像[1,3,5,6,0]这样，nums[mid] > nums[hi]，说明左半边1,3,5是升序的。
• 如果1 <= target < 5，目标在1,3里，放弃右半边5,6,0
• 否则，目标不在1,3,5里，在剩下的6,0里找。

#### 代码

public class Solution {
public int search(int[] nums, int target) {
if (nums.length == 0) { return -1; }
int lo = 0, hi = nums.length-1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) { return mid; }
if (nums[mid] < nums[hi]) { // right half is sorted, ex:[7,0,1,3,5,6]
if (nums[mid] < target && target <= nums[hi]) { // target can only be in right half
lo = mid + 1;
} else { // target is not in right half
hi = mid - 1;
}
} else { // left half is sorted, ex:[1,3,5,6,0]
if (nums[lo] <= target && target < nums[mid]) { // target can only be in left half
hi = mid - 1;
} else { // target is not in left half
lo = mid + 1;
}
}
}
return -1;
}
}