# Search in Rotated Sorted Array 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, nums, ..., 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 `O(logn)` runtime complexity.

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

Example 3:

```Input: nums = , target = 0
Output: -1

Source: Leetcode
```

Constraints:

• `1 <= nums.length <= 5000`
• `-104 <= nums[i] <= 104`
• All values of `nums` are unique.
• `nums` is an ascending array that is possibly rotated.
• `-104 <= target <= 104`
`spoiler ALERT !!!`

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

1. If mid value >= left value, left part is purely sorted
1. 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.
2. Else, right part is purely sorted
1. 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.
3. 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 &lt;= 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] &lt;= target) &amp;&amp; (target &lt; nums[mid]) )
right = mid - 1;
else
left = mid + 1;
}

else{ // right side is pure
if( (nums[mid] &lt; target) &amp;&amp; (target &lt;= 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 &lt;= 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] &lt;= target and target &lt; nums[mid]:
right = mid - 1
else:
left = mid + 1

else: #right side is pure
if nums[mid] &lt; target and target &lt;= 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 &lt;= 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] &lt;= target) &amp;&amp; (target &lt; nums[mid]) )
right = mid - 1;
else
left = mid + 1;
}

else{ // right side is purely sorted
if( (nums[mid] &lt; target) &amp;&amp; (target &lt;= nums[right]) )
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}```

#### Comparison Between Two Approaches

So, Binary search is the winner for time complexity.