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

{% hint style="info" %}
因為數列在某個index被旋轉過，所以要先確認mid位置和前半還是後半是有序的遞增數列。然後就可以分別討論前半有序和後半有序的情形去做binary search。
{% endhint %}

```cpp
// Binary Search
int search(vector<int>& nums, int target) { // time: O(logn); space: O(1)
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) { // [left...mid] is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1; // the equal case is handled beforehand
            }
        } else { // [mid...right] is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    } 
    return -1;
}
```

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

{% content-ref url="81.-search-in-rotated-sorted-array-ii" %}
[81.-search-in-rotated-sorted-array-ii](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/binary-search/81.-search-in-rotated-sorted-array-ii)
{% endcontent-ref %}