Find the minimum element in a sorted and rotated array


We are given a sorted array that is rotated by some index. We have to find the minimum element in the rotated array.

For example the given sorted array is [1, 2, 3, 4, 5, 6]. Suppose it is rotated left by 3.
The sorted rotated array will be [4, 5, 6, 1, 2, 3]
Here we have to find the minimum element which is 1.

Ideally we can search the minimum element from this array by checking each element and comparing it against the minimum element. But this will be a linear search and will take O(n) time if the element is at the last index

Since the array is sorted, we can do better in searching the min element by using a binary search.
Binary search is a search mechanism where we divide the array and look for the array in that part of array, essentially dividing our search size into half. But, here since the array is also rotated, we need to check for few additional conditions since the minimum element is no longer at the first position

 

Understand binary search for sorted and rotated array

When we closely look at the sorted and rotated array, there are 3 different cases that are possible.
And it does not matter whether the array is right rotated or left rotated

Case 1: Array is not rotated at all
  • Example: int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}
  • In this case the min element is at the first position and the max element is at the last position
  • arr[0] < arr[arr.length-1] holds true in this case

 

Case 2: Minimum element is to the right side of middle element
  • Example: int[] arr = {4, 5, 6, 7, 8, 9, 1, 2, 3}
  • In this case, the element in the middle is greater than the leftmost and rightmost element
  • Element 8 is greater then 4 and 3
  • To do a binary search in the right side of mid element 8, we can compare element at mid position with element at last position
  • array[mid] > array[last] holds true in this case

 

Case 3: Minimum element is to the left side of middle element
  • Example: int[] arr = {7, 8, 9, 1, 2, 3, 4, 5, 6}
  • In this case, the element in the middle is less than the leftmost and rightmost element in the array
  • Element 2 is less then 7 and 6 and the min element falls to the left of 2, so we want to search in the left side of mid element
  • In this case if you notice, the condition for case 2 array[mid] > array[right] becomes false
  • This means when the condition for case 2 is false, we can safely assume the min element will be on the left side of mid element

 

Algorithm

  1. Initialize the first, last element
  2. loop while first is less than last element
    • Initialize mid element
    • If the mid element is greater than last element then search in right half
    • Else search in left half
  3. return first element

 

Code

#Java Code

class FindMinInSortedRotatedArray{

    public static int findMin(int array[])
    {
        int first = 0;
        int last = array.length - 1;
        while(first < last) 
        {
            int mid = first + (last - first) / 2;
            if(array[mid] > array[last]){
                first = mid + 1;
            } 
            else{
                last = mid;
            }
        }
        return array[first];
    }
    
    public static void main(String[] args)
    {
        int array[] = {7, 8, 1, 2, 3, 4, 5, 6};
        
        FindMinInSortedRotatedArray fm = new FindMinInSortedRotatedArray();
        int n = fm.findMin(array);
        
        System.out.println("Minimum element in the sorted and rotated array is : " + n);
    }

}
Output

Minimum element in the sorted and rotated array is : 1



Thanks for feedback.



Read More....
Check if an array is a min heap
Convert a sorted array into a binary search tree - recursive approach
Print the elements of an array
Find the kth largest element in the array
Find the kth smallest element in the array
Merge two sorted arrays