153. Find Minimum in Rotated Sorted Array

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Optimal Solution (Binary Search)

In the binary search solution, it is essential to exclude the half in which the answer may not reside. Initially, determine which half constitutes the sorted portion. This sorted half can be identified by comparing the middle value with the low and high values. In the case of a rotated sorted array, there is a high probability that the minimum value is not present in the sorted half. If it does exist, the minimum value corresponds to the element at the low or first index. Therefore, we eliminate the sorted half by extracting crucial information, such as the minimum element within it. Following the elimination of the sorted half, we shifted our focus to the unsorted area and continued the search.

tip: Binary Search template

While(low<=high)

low = mid +1

high = mid -1

Always use the above template for binary search.

Code 1

class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length-1;
        int ans = nums[0];

        while(low<=high){
            int mid = (low+high)>>1;

            if(nums[low]<=nums[mid]){
                ans = Math.min(ans, nums[low]);
                low = mid+1;
            } else{
                ans = Math.min(ans, nums[mid]);
                high = mid-1;
            }
        }
        return ans;
    }
}

Code 2

We can also optimize our approach, by keeping a check if the given array is not rotated we can directly compare our answer with a low index element stop the process.

class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length-1;

        int ans = nums[0];

        while(low<=high){
            int mid = (low+high)>>1;

            if(nums[low]<=nums[high]) {
                ans = Math.min(ans, nums[low]);
                break;
            }

            if(nums[low]<=nums[mid]){
                ans = Math.min(ans, nums[low]);
                low = mid+1;
            } else{
                ans = Math.min(ans, nums[mid]);
                high = mid-1;
            }
        }
        return ans;
    }
}

Code 3

Another Version of Binary Search

class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length-1;


        while(low<=high){
            if(nums[low]<=nums[high]) return nums[low];

            int mid = (low+high)>>1;

            if(mid-1>=0 && mid+1<nums.length && 
            nums[mid-1]>nums[mid] && nums[mid]<nums[mid+1]) return nums[mid];

            if(nums[mid]<nums[low] && nums[mid]<nums[high]){
                high = mid -1;
            } else{
                low = mid +1;
            }

        return -1;
    }
}