---
# System prepended metadata

title: LC 33. Search in Rotated Sorted Array
tags: [medium, leedcode, Binary Search, python, c++]

---

# LC 33. Search in Rotated Sorted Array

### [Problem link](https://leetcode.com/problems/search-in-rotated-sorted-array/)

###### tags: `leedcode` `python` `c++` `medium` `Binary Search`

There is an integer array <code>nums</code> sorted in ascending order (with  **distinct**  values).

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

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

You must write an algorithm with <code>O(log n)</code> 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:** 

- <code>1 <= nums.length <= 5000</code>
- <code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code>
- All values of <code>nums</code> are  **unique** .
- <code>nums</code> is an ascending array that is possibly rotated.
- <code>-10<sup>4</sup> <= target <= 10<sup>4</sup></code>


## Solution 1 - Binary Search
#### Python
```python=
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] >= nums[left]:
                if nums[left] <= target <= nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] <= target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1
```
#### C++
```cpp=
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n - 1;

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

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[n - 1]) {
                if (target > nums[n - 1] && nums[mid] >= target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target > nums[n - 1] || nums[mid] >= target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        if (left == n || nums[left] != target) {
            return -1;
        }
        return left;
    }
};
```

>### Complexity
>n = nums.length
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(logn)         | O(1)             |


## Note
sol1:
ex: [4, 5, 6, 7, 0, 1, 2]
![image](https://hackmd.io/_uploads/Bk2mKaZIA.png)
```python!
分情況去想:
if nums[mid] > nums[-1]:
    if target > nums[-1]: # 此時nums[mid]與target都在紅線上
        if nums[mid] >= target:  # 代表mid右側都不要了
            right = mid - 1;
        else:  # 代表mid左側都不要了
            left = mid + 1;
    else: # 此時nums[mid]在紅線上, target在綠線上, 所以mid左側的都不要了
        left = mid + 1;
else:
    if target > nums[-1]: # 此時nums[mid]在綠線上, target在紅線上, 所以mid的右側都不要了
        right = mid - 1;
    else:  # 此時nums[mid]與target都在綠線上.
        if nums[mid] >= target:
            right = mid - 1;
        else:
            left = mid + 1;
```
