Find Minimum in Rotated Sorted Array

DevSniper
Published : 25 July 2024

107 Views

Array Coding Problems DSA Challange Binary Search

Given a rotated sorted integer array with distinct values of size N. Your task is to find the minimum value within the array.

Example 1 :-

arr : [5,7,9,2,3,4]

Output : 2

Example 2 :-

arr : [13,15,3,4,6,7,9]

Output : 3

Example 3 :-

arr : [2,5,6,7,8,9]

Output : 2

Constraints :

1 <= arr.length <= 5000
-10^4 <= nums[i] <= 10^4
All values of arr are distinct/unique.

Brute force (Naive) Approach

The brute force approach involves iterating through the array and find the minimum element from the array (linear search).

C++

Java

Python

#include <bits/stdc++.h>
using namespace std;

int FindMininum(int arr[], int n)
{
    int min=INT_MAX;
    for(int i=0; i<n; i++) {
        if(arr[i]<min) {
            min=arr[i];
        }
    }
    return min;
}
int main()
{
    int arr[] = {6,8,2,3,5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<FindMininum(arr,n)<<endl;
}

Time Complexity : O(N)

Space Complexity : O(1)

Using Binary Search

Binary search is a highly effective method for finding elements in a sorted array. In our case of a rotated sorted array. Here direct binary search is not feasible due to rotation but we can modify binary search here to find the minimum value efficiently.

Idea of modified Binary Search : When dividing array into to halves (calculating mid), at least one half of the array remains sorted at any given point, so by determining which half is sorted. We can efficiently decide where to continue our search using binary search.

Steps :

Create 3 variables minimum ( assign with maximum value) ,left (0) and right(N-1)
Iterate until left is less than equal to right (similar as Binary Search).
Calculate mid point of left and right point.
Identify is left half sorted or right half sorted.
if left half sorted
- if left most element is less than current minimum update current minimum.
- skip left half ( move left to mid+1)
if right half sorted
- if mid element is less than current minimum update current minimum.
- skip right half ( move right to mid -1 )

C++

Java

Python

#include <bits/stdc++.h>
using namespace std;

int FindMinimum(int arr[], int n)
{
    int left=0,right = n-1;
    int ans=INT_MAX;
    while(left<=right) {
        int mid=(left+right)/2;
        // left half is sorted
        if(arr[left]<=arr[mid]) {
            ans=min(ans,arr[left]);
            left=mid+1;
        } else {
            // right half is sorted
            ans= min(ans,arr[mid]);
            right=mid-1;
        }
    }
    return ans;
}
int main()
{
    int arr[] = {5,6,7,8,9,10,3,4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<FindMinimum(arr,n);
}

Time Complexity : O(logN)

Space Complexity : O(1)