# 33. Search in Rotated Sorted Array 搜索旋转排序数组

@TOC

## # 题目描述

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
``````

## # 解题方法

（1）如果target==A[m]，那么m就是我们要的结果，直接返回； （2）如果A[m]<A[r]，那么说明从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。 （3）如果A[m]>=A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。

``````class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums: return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) / 2
if nums[mid] == target:
return mid
if nums[mid] < nums[right]:
if target > nums[mid] and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
else:
if target < nums[mid] and target >= nums[left]:
right = mid - 1
else:
left = mid + 1
return -1
``````

C++代码如下：

``````class Solution {
public:
int search(vector<int>& nums, int target) {
const int N = nums.size();
// [l, r)
int l = 0, r = N - 1;
while (l <= r) {
int mid = l + (r - l) / 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;
}
};
``````

## # 日期

2018 年 3 月 12 日 2019 年 1 月 11 日 —— 小光棍节？