153. Find Minimum in Rotated Sorted Array

//🎯DAY 24 PROBLEM 1
//The idea of the problem is binary search. In binary search, two things are needed when to return the answer and then the condition that decides where to go first half or
// second half. In normal binary search,if nums[mid]<target then we go to second larger half i.e. start=mid+1.
//Here, eg 22 23 24 1 2 3 so mid comes 24 we check whether start< or>mid if start<mid like 22<24, the lower half array is sorted and the min element is always present in unsorted
//array so the search space reduces to half i.e. second half of sorted array.
//✔️✔️Key Takeaways from the problem:Even, after building the solution, always run the array problem on size 1 input, in most of the cases the normal solution gives runtime error
//class Solution {
    int binarySearch(vector<int>&nums, int start, int end)
    {
        int mid=start + (end-start)/2;
        if(start<=end)
        {
        //❌❌Do not write nums[mid-1]
        //✔️✔️Instead use nums[(N+mid-1)%N] where N=nums.size(), this is done to prevent overflow as in the case of 2,1 the mid comes out to be 0 and then mid-1 is not a defined 
        //index, rather the previous of element 2 is 1 in a rotated array so we return (2+0-1)%2 as the index i.e 1 element
        if(nums[(nums.size()+mid-1)%nums.size()]>nums[mid])
            return nums[mid];
        if(nums[mid]<nums[end])
            return binarySearch(nums,start,mid-1);
        if(nums[mid]>=nums[end])
            return binarySearch(nums,mid+1,end);
        }
        return nums[mid];
    }
public:
    int findMin(vector<int>& nums) {
        //⚠️⚠️if size is 1, then mid-1 gives overflow, so return here only 
        if(nums.size()==1)
            return nums[0];
        if(nums[0]<nums[nums.size()-1])
            return nums[0];
       return binarySearch(nums,0,nums.size()-1); 
    }
};