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

Initialize the first, last element
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
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

Dislike

Thanks for feedback.