33. Search in Rotated Sorted Array
一、题目
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 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.
二、分析
rotated之后的数组是无序的。但是，它可以以最小值为界分为前后两个子数组，而这两个数组都是有序的。我们可以首先确定要找的数target在哪个子数组，然后在哪个子数组进行binary_search即可。
1，找最小值所在位置
1 int getMinIndex(vector<int>& nums) {
2 int length = nums.size();
3 if (length == 0)
4 return 0;
5 int left = 0, right = length -1, mid = 0;
6
7 while (left < right) {
8 if (nums[left] < nums[right])
9 //return nums[left];
10 return left;
11 mid = left + (right - left) / 2;
12 if (nums[mid] <= nums[right])
13 right = mid;
14 else
15 left = mid + 1;
16 }
17 //return nums[left];
18 return left;
19 }
2，binary_search
1 int binary_search(vector<int> &nums, int target, vector<int>::iterator iterLeft, vector<int>::iterator iterRight) { 2 while (iterLeft <= iterRight) { 3 auto mid = iterLeft + (iterRight - iterLeft) / 2; 4 if (*mid < target) 5 iterLeft = mid + 1; 6 else if (*mid > target) 7 iterRight = mid - 1; 8 else 9 return mid - nums.begin(); 10 } 11 return -1; 12 }
3, 找target的位置
1 int search(vector<int>& nums, int target) {
2 vector<int>::iterator iterLeft = nums.begin(), iterRight = nums.end() - 1;
3 if (nums.size() == 0)
4 return -1;
5 if (*iterLeft < *iterRight) { //array not be rotated
6 return binary_search(nums, target, iterLeft, iterRight);
7 }
8 else {
9 int index = getMinIndex(nums);
10 if (target <= *iterRight) {
11 iterLeft += index;
12 return binary_search(nums, target, iterLeft, iterRight);
13 }else {
14 iterRight = iterLeft + index;
15 return binary_search(nums, target, iterLeft, iterRight);
16 }
17 }
18 }
4，总结前三点，总代码如下
1 class Solution { 2 public: 3 int getMinIndex(vector<int>& nums) { 4 int length = nums.size(); 5 if (length == 0) 6 return 0; 7 int left = 0, right = length -1, mid = 0; 8 9 while (left < right) { 10 if (nums[left] < nums[right]) 11 //return nums[left]; 12 return left; 13 mid = left + (right - left) / 2; 14 if (nums[mid] <= nums[right]) 15 right = mid; 16 else 17 left = mid + 1; 18 } 19 //return nums[left]; 20 return left; 21 } 22 23 int search(vector<int>& nums, int target) { 24 vector<int>::iterator iterLeft = nums.begin(), iterRight = nums.end() - 1; 25 if (nums.size() == 0) 26 return -1; 27 if (*iterLeft < *iterRight) { 28 return binary_search(nums, target, iterLeft, iterRight); 29 } 30 else { 31 int index = getMinIndex(nums); 32 if (target <= *iterRight) { 33 iterLeft += index; 34 return binary_search(nums, target, iterLeft, iterRight); 35 }else { 36 iterRight = iterLeft + index; 37 return binary_search(nums, target, iterLeft, iterRight); 38 } 39 } 40 } 41 42 int binary_search(vector<int> &nums, int target, vector<int>::iterator iterLeft, vector<int>::iterator iterRight) { 43 while (iterLeft <= iterRight) { 44 auto mid = iterLeft + (iterRight - iterLeft) / 2; 45 if (*mid < target) 46 iterLeft = mid + 1; 47 else if (*mid > target) 48 iterRight = mid - 1; 49 else 50 return mid - nums.begin(); 51 } 52 return -1; 53 } 54 55 };
三、另一种“非常规”解法
首先，我们还是找到最小值的位置，也就是两个有序子数组的分界点，记为rot。然后，取rotated数组（长度为n）的mid，那么（rot+mid）%n即unrotated数组的真实mid位置。
然后，对这个数组进行二分查找。
1 class Solution {
2 public:
3 int search(int A[], int n, int target) {
4 int lo=0,hi=n-1;
5 // find the index of the smallest value using binary search.
6 // Loop will terminate since mid < hi, and lo or hi will shrink by at least 1.
7 // Proof by contradiction that mid < hi: if mid==hi, then lo==hi and loop would have been terminated.
8 while(lo<hi){
9 int mid=(lo+hi)/2;
10 if(A[mid]>A[hi]) lo=mid+1;
11 else hi=mid;
12 }
13 // lo==hi is the index of the smallest value and also the number of places rotated.
14 int rot=lo;
15 lo=0;hi=n-1;
16 // The usual binary search and accounting for rotation.
17 while(lo<=hi){
18 int mid=(lo+hi)/2;
19 int realmid=(mid+rot)%n;
20 if(A[realmid]==target)return realmid;
21 if(A[realmid]<target)lo=mid+1;
22 else hi=mid-1;
23 }
24 return -1;
25 }
26 };