> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/search/33search-in-rotated-sorted-array.md).

# 33\_Search in Rotated Sorted Array

\[Medium]\[Array, Binary Search]

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.

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

## Solution

**Idea**: **Binary Search**

* Since the array is rotated sorted, there must be one side that is in ascending order. Find that side and check if the target is in this side. If yes, throw away the other side. If no, throw away this side.
* The most important thing I learn from this problem is don't make the conditions for binary search too complicated. We don't need to specify each nested conditions. We can use one simple condition for one side and else for the other side.

**Time Complexity**: $$O(\log{n})$$

**Space Complexity**: $$O(1)$$

```python
def search(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    left, right = 0, len(nums)-1

    while left <= right:
        mid = left + (right - left)//2
        if nums[mid] == target:
            return mid
        elif nums[left] <= nums[mid]:
            # left half must be sorted
            # test if target is in left half
            if nums[left] <= target < nums[mid]:
                # keep left half
                right = mid - 1
            else:
                # keep right half
                left = mid + 1
        else:
            # right half must be sorted
            # test if target is in right half
            if nums[mid] < target <= nums[right]:
                # keep right half
                left = mid + 1
            else:
                # keep left half
                right = mid - 1
    return -1
```