Minimum Number in sorted rotated array Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/minimum-number-in-a-sorted-rotated-array-1587115620/1

(It is also the problem of the day for 17-05-2022.)

Solution:

class Solution

{

    //Function to find the minimum element in the sorted and rotated array.

    static int minNumber(int arr[], int start, int high)

    {

        int mid=0;

      

        int min=Integer.MAX_VALUE;

        while(start<=high){

            mid=start+(high-start)/2;

            if(min>arr[mid]){

                min=arr[mid];

            }

            if(arr[0]<arr[mid] && arr[mid]>arr[arr.length-1]){

                start=mid+1;

            }

            else if(arr[0]>arr[mid] && arr[mid]<arr[arr.length-1]){

                high=mid-1;

            }

            else if(arr[0]<arr[mid] && arr[mid]<arr[arr.length-1]){

                high=mid-1;

            }

            else{

                start=mid+1;

            }

           

        }

        return min;

    }

}

Time Complexity: O(LogN)[GFG Time:0.94/1.96]

Space Complexity:O(N)[Array is used]

Auxiliary Space: O(1)[A constant is used]

Total Test Cases:121 

Approach Used:

Here first we will see the corner elements and compare them with the mid element

Now four different cases:

1. left small right small

2. left small right big

3. left big right small

4. left big right big

Case 1: 

It means the left side of the mid will be sorted.

So the chance of finding the minimum element is less on the sorted side so we will move to the right side of mid.

start=mid+1;

Case 2: Ascending order

It means both the sides of the mid are sorted.

So the chance of finding the minimum element on the right side is less so we will move to the left side of mid.

end=mid-1;

Case 3: Descending order

It means both the sides of the mid are sorted.

So the chance of finding the minimum element on the left side is less so we will move to the right side of mid.

start=mid+1;

Case 4: 

It means the right side of the mid will be sorted.

So the chance of finding the minimum element is less on the sorted side so we will move to the left side of mid.

end=mid-1;

Here if we observe clearly then we can identify that if the side is sorted then the chances of finding the minimum element would be less. 

It is so because if the sorted array will be rotated then its sorting will get disturbed and its initial elements will also get rearranged due to which the elements afterward initial elements will be in a sorted fashion while initials will be unsorted.

"Thanks For Reading.😇"

"Share further To Increase Knowledge Treasure.😊"