# 33. Search in Rotated Sorted Array

There is an integer array `nums` sorted in ascending order (with distinct values).

Prior to being passed to your function, `nums` is possibly rotated at an unknown pivot index `k` (`1 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` ( 0-indexed ). For example, `[0,1,2,4,5,6,7]` might be rotated at pivot index `3` and become `[4,5,6,7,0,1,2]`.

Given the array `nums` after the possible rotation and an integer `target`, return the index of`target` if it is in`nums` , or`-1` if it is not in`nums`.

You must write an algorithm with `O(log n)` runtime complexity.

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

Example 3:

``````**Input:** nums = [1], target = 0
**Output:** -1
``````

Constraints:

• `1 <= nums.length <= 5000`
• `-10^4 <= nums[i] <= 10^4`
• All values of `nums` are unique.
• `nums` is an ascending array that is possibly rotated.
• `-10^4 <= target <= 10^4`

0 1 2 4 5 6 7

7 0 1 2 4 5 6

6 7 0 1 2 4 5

5 6 7 0 1 2 4

4 5 6 7 0 1 2

2 4 5 6 7 0 1

1 2 4 5 6 7 0

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

0 1 2 4 5 6 7

7 0 1 2 4 5 6

6 7 0 1 2 4 5

5 6 7 0 1 2 4

4 5 6 7 0 1 2

2 4 5 6 7 0 1

1 2 4 5 6 7 0

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

Github 同步地址：

https://github.com/grandyang/leetcode/issues/33

Search in Rotated Sorted Array II

Find Minimum in Rotated Sorted Array

Pour Water Between Buckets to Make Water Levels Equal

https://leetcode.com/problems/search-in-rotated-sorted-array/

https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14436/Revised-Binary-Search

https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14435/Clever-idea-making-it-simple

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation