# Search in Rotated Sorted Array

## Problem

You are given an integer array `nums` sorted in ascending order, and an integer `target`.

Suppose that `nums` 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]`).

*If `target` is found in the array return its index, otherwise, return `-1`.*<br>

{% hint style="info" %}
For example:

```
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
```

```
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
```

{% endhint %}

### Thought Process

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MNKOReiY9AnXJ_g4N6g%2F-MNKn0Bczzi_SxvFGXX8%2FIMG_2B4CA978C8C0-1.jpeg?alt=media\&token=8ec29be8-bb85-46ae-99ec-c7397e52a3dc)

* Because the array is not fully sorted, we can't apply regular binary search (because the ranges are all messed up since it is rotated)

* Since the array was sorted in ascending order before it was rotated, we can utliize this fact to look in between the ranges of the the rotated array to see which half is sorted.

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MNKOReiY9AnXJ_g4N6g%2F-MNKnYFbRUyR1C1US_Af%2FIMG_325740FF1956-1.jpeg?alt=media\&token=764acdde-7524-4907-8c68-c16addb6db78)

## Solution

```
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums)-1
        
        while low <= high:
            mid = low + (high-low)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] <= nums[high]:
                if target > nums[mid] and target <= nums[high]:
                    low = mid+1
                else:
                    high = mid - 1 #the case where target is less than mid
            elif nums[low] <= nums[mid]:
                if target >= nums[low] and target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid+1
        return -1
```

### Follow up:&#x20;

*What if the array contained duplicates?*

* If the array contains duplicates, the mid will be the same as the low index (we know this because the array is sorted in ascending order). If this is the case, we just keep increasing low index.To explain why, consider this sorted array `1111115`, which is rotated to `1151111` . Assume `left = 0` and `mid = 3`, and the *target* we want to search for is `5`. Therefore, the condition `A[left] == A[mid]` holds true. We need to keep increasing the lower index.

```
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        low, high = 0, len(nums)-1
        
        while low <= high:
            mid = low + (high-low)//2
            if nums[mid] == target:
                return True
            
            elif nums[mid] == nums[low]:
                low+=1
            
            elif nums[mid] <= nums[high]:
                if target > nums[mid] and target <= nums[high]:
                    low = mid+1
                else:
                    high = mid - 1 #the case where target is less than mid
            elif nums[low] <= nums[mid]:
                if target >= nums[low] and target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid+1
        return False
            
        
```

## Key Points

* This problem is all about searching in the right sorted range.

* We need to check if the ranges are increasing and if so, check if the target fits between those ranges

* If our array contauns duplicates, the mid will be the same as low so we must increase the lower index.

## Time Complexity

* **Time:** $$O(log(n))$$&#x20;
* **Space:** $$O(1)$$&#x20;