Find Minimum in Rotated Sorted Array

Suppose you have given an array sorted in ascending order. The array is rotated at some unknown pivot point. Following the example of a sorted rotated array.

[0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]

Find the minimum element from the array. You may assume no duplicate exists in the array.

Example 1:

Input: [8,9,10,1,2,4] 
Output: 1

Example 2:

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

The brute force approach to solve this problem is to search the entire array and find the minimum element. The time complexity for that would be O(N) given that N is the size of the array. But we can do better with the Binary Search algorithm. Binary Search can solve the problem in O(logN) time. Since the given array is sorted, we can make use of Binary Search. However, the array is rotated. So simply applying the binary search won’t work here. So we can use a slightly modified version of Binary Search to solve the problem. So there are 2 conditions to apply with the modified version of Binary Search.

If the array is not rotated then A[0] is the smallest element of the sorted array. How to find if the array is not rotated?  Simple last element of the array > first element.

Otherwise, calculate the mid of the array by left + (right-left)/2. Until you find A[mid] > A[mid+1].

Once you find A[mid] > A[mid+1] then A[mid+1] is the smallest element of the array.

Rotated Sorted Array

Following is the Java Implementation:

class Solution {
  public int findMin(int[] nums) {
    if (nums == null || nums.length == 0)
      return -1;
    if (nums.length == 1) return nums[0];
    int left = 0, right = (nums.length - 1);
    if (nums[left] <= nums[right]) return nums[left];
    while (left < right) {
      int pivot = left + (right - left) / 2;
      if (nums[pivot] > nums[pivot + 1]) return nums[pivot + 1];
      if (nums[pivot] > nums[left]) left = (pivot + 1);
      else right = pivot;
    }
    return -1;
  }
}

Complexity Analysis

  • Time Complexity: Same as Binary Search O(logN)
  • Space Complexity: O(1)

Categories: Binary Search

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s