LeetCode 153. Find Minimum in Rotated Sorted Array

Problem Statement :

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

Level: Medium

Approach -

1. In the first approach, we can use the brute force method of Linear Search and return the minimum element after traversing the array in O(n) time complexity and O(1) space complexity.
2. In the second approach, we will be using an optimal way to find the minimum element using Binary Search.

In this approach, we will be starting with edge cases and some conditions:

Since it is given that the Length of the array is greater than 0, the first condition will be if there is only a single element in the array.

In that case, we will return that element as it will be the minimum.

In the Second Condition, we need to check if the array is rotated 0 or n times, where n is the number of elements in an array.
See example below -

After checking these two conditions, we will apply Binary Search by taking the below-listed variables -

Initializing minimum element variable, min = Integer.MAX_VALUE
Length of array, L = array.length
Start Index, s =0
End Index, e = L-1
Mid Index, m=0

If the element in the middle is greater than the element in the end, then we need to shift the start index, next to the mid.
else if the element in the middle is smaller than the end element then we need to shift the end index to the mid, as we need to take the mid element alo in account.

When all the indexes are pointing towards the same element, then that is our answer.

class Solution {
    public int findMin(int[] nums) {
        int L = nums.length;
        if(L==1){
            return nums[0];
        }
        else if (nums[0]<nums[L-1]){
            return nums[0];
        }

        int min = Integer.MAX_VALUE, s =0, e = L-1,m=0;
        while(s<=e){
            m = (s+e)/2;
            if(nums[m]>nums[e]){
                s = m+1;
            }else{
                e=m;
            }
            if(s==m && m==e){
                break;
            }
        }
        return nums[m];
    }
}

Example -

Hand-written example

Solution on Leetcode — Click Here

Happy Coding!!!
Do clap if you like the Solution.
Any queries or suggestions? Sure!! Ping me :
* LinkedIn
* Twitter
* GitHub
* Medium