33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order 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.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

---

这一题和LeetCode Find Minimum in Rotated Sorted Array类似，只不过不是查找最小值，而是查找某个target是否存在。也是采用二分查找的思路，首先判断nums[m]和nums[r]的关系，如果nums[m]<nums[r]，说明右半部分是有序的，看看target是否在该部分范围内，如果在，则l=mid+1；否则r=mid-1。如果nums[m]>nums[r]，说明右半部分无序，则左半部分有序，看看target是否在左半部分范围内，如果在，则r=mid-1；否则l=mid+1。如此循环下去。

完整代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target)
    {
        int l = 0, r = nums.size() – 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[mid] < nums[r]) {
                if (target > nums[mid] && target <= nums[r]) {
                    l = mid + 1;
                }
                else {
                    r = mid – 1;
                }
            }
            else {
                if (target >= nums[l] && target < nums[mid]) {
                    r = mid – 1;
                }
                else {
                    l = mid + 1;
                }
            }
        }
        return -1;
    }
};

本代码提交AC，用时9MS。

二刷。用递归方法实现，每次判断区间的左边是否小于右边，如果是的话，说明是有序的，常规二分即可；如果不是，则取中点，递归在其左边和右边搜索。由于取了中点后，必定有一边是有序的，则要么在有序区间搜索，要么在另一边搜索，即每次是减半的，所以时间复杂度也是O(lgN)。

完整代码如下：

class Solution {
public:
	int BinarySearch(vector<int>& nums, int target, int left, int right) {
		if (left > right)return -1;
		if (left == right) {
			if (nums[left] == target)return left;
			else return -1;
		}
		if (nums[left] < nums[right]) {
			if (target >= nums[left] && target <= nums[right]) {
				int mid = left + (right - left) / 2;
				if (nums[mid] == target)return mid;
				else if (nums[mid] < target)return BinarySearch(nums, target, mid + 1, right);
				else return BinarySearch(nums, target, left, mid - 1);
			}
			else {
				return -1;
			}
		}
		else {
			int mid = left + (right - left) / 2;
			int lans = BinarySearch(nums, target, left, mid);
			int rans = BinarySearch(nums, target, mid + 1, right);
			if (lans != -1)return lans;
			if (rans != -1)return rans;
			return -1;
		}
	}
	int search(vector<int>& nums, int target) {
		return BinarySearch(nums, target, 0, nums.size() - 1);
	}
};

本代码提交AC，用时0MS。

三刷。迭代方法还是主流，和常规二分搜索的代码框架是一致的。但是一刷的时候是先判断右半部分是否有序，有点不符合直觉，如果简单的先判断左半部分，会出bug，比如[3,1]，要找1的时候，此时m=0，和l=0是相同的，如果简单的用nums[l]<nums[m]来判断左边是否有序的话，会有问题，此时m==l，所以左边也可以看做是有序的，但不满足nums[l]<nums[s]。所以需要额外加一个l==m的判断。完整代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l <= r) {
            int m = l + (r - l) / 2;
            if(nums[m] == target) return m;
            
            if(l == m || nums[l] < nums[m]) { // l == m 左边只有一个元素，左边也是有序的
                if(target >= nums[l] && target < nums[m]) r = m - 1;
                else l = m + 1;
            } else {
                if(target > nums[m] && target <= nums[r]) l = m + 1;
                else r = m - 1;
            }
        }
        
        return -1;
    }
};

本代码提交AC， 用时8MS。