# 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:**

Output: 4

Output: -1

Output: -1

**Constraints:**

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

## Solution 1 - Binary Search
#### 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++

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++ (簡化版)

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]

分情況去想:
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;