Home Arrays [Leetcode] – Search in a Rotated Sorted Array Solution

[Leetcode] – Search in a Rotated Sorted Array Solution

by nikoo28
0 comment

Question: You need to search for a target value in a rotated sorted array. If the value is present, return the index.

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

Let us try to understand the problem statement and its test cases first.

You have an array, that is sorted, but it is rotated by an unknown number of times. Let us say the initial sorted array is [0, 1, 2, 4, 5, 6, 7].

Rotating it 1 time: [7, 0, 1, 2, 4, 5, 6] Rotating it 2 times: [6, 7, 0, 1, 2, 4, 5]
Code language: CSS (css)

This is how you rotate an array. On a side note, you can find a sample problem on array rotation as well. It will be a good idea to understand it first.

However, this problem is a bit different as the rotations of array are unknown.

For a test case, you are given an array [4, 5, 6, 7, 0, 1, 2]. You can find the target element 0 at position number 4.

image showing sample test cases
Fig: Sample test cases

If you can’t find the target element in the array, you simply need to return a -1.

Brute Force Method

A brute force method to solve the problem would be pretty straight forward. Let us say you have to search in this rotated sorted array. The target value is 7.

image showing a sample rotated sorted array
Fig: Sample rotated sorted array

We cannot apply any efficient searching technique directly in this array as it has been rotated unknown number of times. However, you can iterate over the array and try to find the pivot element. The pivot element is the element about which the array has been rotated. Once you find this element, in the above example it is at position 3, you can now un-rotate the array such that the element at position 0 is the lowest element.

image showing un-rotating an array
Fig: Undo rotations in array

Since, the array is now un-rotated, you can simply apply the Binary Search technique to search for the target element. This method works perfectly, but it takes a lot of time to un-rotate. We might as well do a linear search to find the element. We are also never taking any advantage of the fact that it is an already sorted array.

Method 1: Searching for the pivot element

We can actually search for the pivot element efficiently in the array. Let us take up the same array once again.

Image showing a sample rotated sorted array
Fig: Sample rotated sorted array

If you look closely in the array, a pivot element has some special property. The element left to pivot and right to pivot, both of them would be greater than it. Try to write down some sample cases on your own to understand this, as it is quite crucial for understanding the solution.

Using this property, we can apply a Binary Search algorithm on the array to find the pivot element.

Image showing the pivot element
Fig: Finding the pivot element

As soon as you find the pivot element, you can separate the array into two halves. If you look at the halves, they are in a sorted order. This is because the array is already sorted. It has been just rotated by some number of times.

Image showing splitting of array to 2 sorted arrays
Fig: Splitting the array to 2 sorted arrays

As soon as you split the array in 2 parts, you can again apply the binary search algorithm on each of them to determine if the target element is present or not.

The time complexity of this approach is O(\log n), and it is a perfectly valid solution. However, you are doing the binary search twice on the array. Can you achieve the same result using binary search just once?

Method 2: Using Modified Binary Search

I like to call this method the modified binary search. To understand it, let us take up the example array once again. This array is a rotated sorted array and the target value is 9.

image showing sorted rotated array
Fig: Sample array

The core concept of a binary search algorithm is that at every iteration, you discard one half of the array. What happens when you try to bisect this original array in 2 parts?

Image showing splitting of array
Fig: Splitting an array from middle

As soon as you bisect the array in 2 halves, you obtain 2 arrays. One sub-array will be sorted completely, and the other sub-array will again be a rotated sorted array. This is the core idea behind this solution. No matter, what position you bisect the array, you will always get one sub-array that is sorted.

It then gets very easy to determine if you can find the element in a sorted array. You can just look at the first and last elements. If yes, just proceed with a regular binary search, else you can again bisect the remaining sub-array.

At every step, you will be able to discard one half of the array. Hence, using a recursion based algorithmic paradigm, you can continue narrowing down the search space.

Image showing discarding of sub-arrays
Fig: We can discard one sub-array at every step.

At the very end, if the element is found, you can return the index, else just return a -1.

Implementation:

private int modifiedBinarySearch(int[] arr, int target, int left, int right) { // Not found if (left > right) return -1; // Avoid overflow, same as (left + right)/2 int mid = left + ((right - left) / 2); if (arr[mid] == target) return mid; // Found // If left half is sorted if (arr[mid] >= arr[left]) { // If key is in left half if (arr[left] <= target && target <= arr[mid]) return modifiedBinarySearch(arr, target, left, mid - 1); else return modifiedBinarySearch(arr, target, mid + 1, right); } else { // If right half is sorted // If key is in right half if (arr[mid] <= target && target <= arr[right]) return modifiedBinarySearch(arr, target, mid + 1, right); else return modifiedBinarySearch(arr, target, left, mid - 1); } }
Code language: Java (java)

Time Complexity: O(\log n)
Space Complexity: O(1)

As always, the full implementation and corresponding test cases is available on Github.

Video Explanation

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More