Minimum in a Sorted and Rotated array

Find Minimum in a Sorted and Rotated array

Understanding The Problem

Problem Description: You have a sorted and rotated array where elements are sorted and rotated circularly. Write a program to find the minimum element in the array.

Suppose the elements in array are [1, 2, 3, 4, 5, 6, 7], then rotating by three time array becomes [4, 5, 6, 7, 1, 2, 3].
You won’t be provided with number times array is rotated.
The array will not contain duplicates.

Examples

Input: array[] = [4, 5, 6, 7, 1, 2, 3]
Output: 1

Input: array[] = [8, 9, 4, 5, 6, 7 ]
Output: 4

Input: array[] = [3, 4, 5, 6, 7]
Output: 3

Input: array[] = [3, 2]
Output: 2

Solutions

We will be discussing two solutions to this problem:

Brute force approach (Linear Search ): Traverse the complete array and find the minimum.
An approach similar to Binary Search : Compare mid with first and last element of the subarray and move accordingly.

1. Brute force approach(Linear Search)

The idea is to traverse the array from the first element to the last element of the array and maintain a minimum.

Solution steps

Create a min variable and initialize it with INT_MAX
Iterate over the array and update the min variable with the minimum of min and each element of the array.

Pseudo Code

int findMin(int array[], int size)
{
    int minimum = INT_MAX
    for(int i=0 to size)
        minimum = min(minimum, array[i])
    return minimum
}

Complexity Analysis

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

Critical Ideas to Think

Why did we initialize the minimum with INT_MAX?
Can we use the property of sorted and rotated array to think of a better solution to reduce the time complexity?

2. An approach similar to Binary Search

If we look closely then you will find that there are at most three cases that could be encountered.

Case 1: The leftmost value is less than the rightmost value in the array. This means that the array is not rotated.
Example: [1 2 3 4 5 6 7 8 9]
Case 2: The value in the middle of the array is greater than the leftmost and rightmost values in the array.
Example: [4 5 6 7 8 9 1 2 3]
Case 3 : The value in the middle of the array is less than the leftmost and rightmost values in the array.
Example: [7 8 9 1 2 3 4 5 6]

if we have case 1 then we just return the leftmost value in the array. If we have case 2, we will try to find the minimum on the right side of the array. If we have case 3, we will try to find the minimum to the left side of the array.

Solution steps

Initialize a left and right variable with 0 and size-1 of the array.
Iterate until left < right

If the value at left is less than the value at right then return value at left.
Initialize mid = (left + right )/ 2
Now compare if the value at mid is greater than the value at right , then we search the minimum in the left part of the array. Update left = mid + 1
Otherwise, we search in the right part of the array. Update right = mid

Pseudo Code - Iterative

int findMin(int array[], int size) 
{
    int left = 0
    int right = size - 1
    while(left < right) 
    {
        if(array[left] < array[right]) // case 1
           return array[left]
        int mid = left + (right-left)/2
        if(array[mid] > array[right])
           left = mid + 1           // case 2
        else
           right = mid              // case 3
    }
return array[left]
}

Pseudo Code - Recursive

// Helper function
int bsearch(int array[], int left, int right)
{
     if(left < right)
     {
         if(array[left] < array[right])             // case 1
             return array[left]
         int mid = left + (right - left)/2
         if(array[mid] > array[right])
             return bsearch(array, mid + 1, right)  // case 2
         else 
             return bsearch(array, left, mid)     // case 3
     }
    return array[left]
}
// Driver function
int findMin(int array[], int size) 
{
    return bsearch(array, 0, size - 1)
}

Complexity Analysis

The above approach looks similar to the idea of the binary search.
Time Complexity = O(log n)
Space Complexity = O(1)

Critical Ideas to Think

Do all the three cases discussed above are handled by the algorithm?
Is it necessary to return array[left] in the end?
Why did we initialize mid with (left + (right-left)/2) instead of (left + right)/2?
Will this approach work if we have duplicates in the array?
Can we solve the problem in O(log n) if we have duplicates in the input array?
Can we think of some different approach to solve this problem?
Prepare a list of problems where we can use the idea similar to a binary search for the solution.