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[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 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 = [1], 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 <= 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:

1. Search in rotated sorted array II
2. Find Minimum in Rotated Sorted Array

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! 🙂