Table of Contents

Leetcode 33. Search in Rotated Sorted Array

**Problem**

There is an integer array `nums`

sorted in ascending order (with **distinct** values).

Prior to being passed to your function, `nums`

is **possibly rotated** at an unknown pivot index `k`

(`1 <= k < nums.length`

) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`

(**0-indexed**). For example, `[0,1,2,4,5,6,7]`

might be rotated at pivot index `3`

and become `[4,5,6,7,0,1,2]`

.

Given the array `nums`

**after** the possible rotation and an integer `target`

, return *the index of *`target`

* if it is in *`nums`

*, or *`-1`

* if it is not in *`nums`

.

You must write an algorithm with

runtime complexity.**O(logn)**

**Example 1:**

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

**Example 2:**

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

**Example 3:**

Input:nums = [1], target = 0Output:-1 Source:Leetcode

**Constraints:**

`1 <= nums.length <= 5000`

`-10`

^{4}<= nums[i] <= 10^{4}- All values of
`nums`

are**unique**. `nums`

is an ascending array that is possibly rotated.`-10`

^{4}<= target <= 10^{4}

spoilerALERT!!!

*If you have come to see the solution before trying to solve it yourself, this really won’t help you, promise! If that is the case, we will recommend, please go back and first try it yourself. If you can’t solve it after (at least)an hour of thinking and trying, please come back! 🙂* You can solve it here.

#### Solution of Search in Rotated Sorted Array (Leetcode 33)

We will see two approaches to solve this problem, Linear and Binary search.

#### Approach-1: Linear Search

##### Analysis

In linear search, we just run a loop through an array or list and check if any element of the array fulfills the condition. In this case, we can do the same i.e. run a loop and check if any value of the array is equal to the target value. If the target is found, we return its index. That’s all!

Below is a simple **pseudocode** of this approach.

```
function search(target, nums[]){
for each
```**i** as index of **nums** array:
if nums[i] == target
return i
}

##### Time Complexity

Since we are traversing each element of the array, in worst case, we will have to go up to the end of array. If there are n elements in the array, we will have to search n elements in worst case. Hence, the time complexity is **O(n)**.

##### Space Complexity

No extra space is being used here. So the space complexity is **O(1)**.

#### Approach-2: Modified Binary Search

Linear search worked well, but there is a better way to improve time complexity to **O(logn) **by applying binary search with a tweak.

##### Analysis

If a sorted array is not rotated, it is easy to find a target value using Binary Search algorithm. Because, we know the target value will be somewhere between the first and the last element of the array. But if we rotate the array, the array no longer remains sorted.

##### Left rotation

Let’s see what happens after some **left rotations** applied to below array.

**(left**, **right** and **mid** indicates the indices of the **first**, **last** and the **middle** element. To understand intensity of each value, let’s imagine a bar chart corresponding each value as shown in the image above.)

After 1 rotation to the left, **10** will take his place right beside **70** and the array will look like below.

We can see the **middle element is changed** from 40 to 50 because of the rotation. Also, we see the array is already not sorted anymore. Now, consider the right side from middle (including the middle element), the values are **50, 60, 70, 10** which is not sorted. But if we see the **left part of the middle** (excluding the middle element), that part is still sorted (**20, 30, 40**). Also note that the middle element (50) is greater than the first element (20).

Now, let’s see how it looks after a 2nd rotation to the left.

20 comes right beside 10, the middle element changes from 50 to 60 and the **left part of the middle element (30, 40, 50) is still sorted**. Interestingly, the middle element (60) is still greater than the first element (30).

Finally, here is what it happens after the third rotation.

Again, left part of middle is still sorted and the right part is not sorted. Middle element is greater than the first one.

At this point, we are not going further with left rotation. The important finding of this experiment is, **if the middle element is greater than the first element, then the left part of the middle element remains sorted**.

**Why do we care which part is sorted and which part is not?** Because, once known, we can easily check if our target value is inside the sorted part or not. If it is in the sorted part, we can apply binary search to find the target. If it is not, we can go to the other part and continue there.

##### Right rotation

After right rotation, the middle element becomes smaller than the first element. Since, middle element is smaller than the first one, we will see **the right part of middle remains sorted** and the left part becomes unsorted. Without blindly agree, let’s see the rotations visually as below.

**How to know which part is sorted?**

The simple rule is,

*if the middle element is greater than the left element, then the left part is sorted. Otherwise, the right part is sorted.*

**The Algorithm**

- If mid value >= left value,
**left part**is purely sorted- Now check if the target is
**between left and mid**or not. If it is, then we will check further the left part only, otherwise we will go to check the right part.

- Now check if the target is
- Else,
**right part**is purely sorted- Now check if the target is
**between mid and right**or not. If it is, then we will check further the right part only, otherwise we will go to check the left part.

- Now check if the target is
- Continue above steps until target not found or left <= right.

##### Time Complexity

Since we are using binary search algorithm with modification, the time complexity is still **O(logn)**.

##### Space Complexity

No extra space is required for this solutions, hence **O(1)** complexity for space.

##### C++ **Code**

class Solution { public int search(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while(left <= right){ int mid = left + (right - left) / 2; if(nums[mid] == target) return mid; else if(nums[mid] >= nums[left]){ // left side is purely sorted if( (nums[left] <= target) && (target < nums[mid]) ) right = mid - 1; else left = mid + 1; } else{ // right side is purely sorted if( (nums[mid] < target) && (target <= nums[right]) ) left = mid + 1; else right = mid - 1; } } return -1; } }

##### Java Code

class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while(left <= right){ int mid = left + (right - left) / 2; if(nums[mid] == target) return mid; else if(nums[mid] >= nums[left]){ // left side is pure if( (nums[left] <= target) && (target < nums[mid]) ) right = mid - 1; else left = mid + 1; } else{ // right side is pure if( (nums[mid] < target) && (target <= nums[right]) ) left = mid + 1; else right = mid - 1; } } return -1; } }

##### Python Code

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

##### C Code

int search(int* nums, int numsSize, int target){ int left = 0; int right = numsSize - 1; while(left <= right){ int mid = left + (right - left) / 2; if(nums[mid] == target) return mid; else if(nums[mid] >= nums[left]){ // left side is purely sorted if( (nums[left] <= target) && (target < nums[mid]) ) right = mid - 1; else left = mid + 1; } else{ // right side is purely sorted if( (nums[mid] < target) && (target <= nums[right]) ) left = mid + 1; else right = mid - 1; } } return -1; }

#### Comparison Between Two Approaches

LINEAR search | BINARY search | |

Time complexity | O(n) | O(logn) |

Space Complexity | O(1) | O(1) |

So, Binary search is the winner for time complexity.

#### Companies asked this question

Facebook, Google, Amazon, Microsoft, Twitter, Linkedin and many more!

#### Similar Problems to solve

If you want to solve more problems like this to improve your problem solving skills, here is the list:

#### Conclusion

Hope you enjoyed this blog. If you do, please feel free to write your comments. If you do not enjoy this, please tell us how we can improve!

Happy Coding! 🙂