[Leetcode] – Search in a Rotated Sorted Array Solution

1.4K

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.

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.

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.

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.

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.

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.

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.

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?

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.

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