Header Ad

Leetcode Find Minimum in Rotated Sorted Array problem solution

In this Leetcode Find Minimum in Rotated Sorted Array problem solution we have 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.

Leetcode Find Minimum in Rotated Sorted Array problem solution


Problem solution in Python.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l , r = 1,len(nums)-1
        
        while l<=r:
            m = l + (r-l)//2
            if nums[m]<nums[m-1]:
                return nums[m]
            if nums[m]<nums[0]:
                r = m
            else:
                l = m + 1
                
        return nums[0]



Problem solution in Java.

public int findMin(int[] nums) {
    return binarySearch(nums,0,nums.length-1);
}
private int binarySearch(int[] nums,int l,int h){
    if(l == h) return nums[l];
    if(l == h-1) return Math.min(nums[l],nums[h]);
    if(nums[l] < nums[h]) return nums[l];
    int m = (l+h)/2;
    if(nums[m] < nums[l] && nums[m] < nums[h]) return binarySearch(nums,l,m); 
    else return binarySearch(nums,m,h);
}


Problem solution in C++.

int findMin(vector<int>& nums) {
        int left=0;
        int right=nums.size()-1;
        int ans=nums[0];
        while(left<=right){
            int mid=(left+right)/2;
            ans=min(ans,nums[mid]);
            if(nums[mid]<nums[right])
                right=mid-1;
            else
                left=mid+1;
        }
        return ans;
    }


Problem solution in C.

int findMin(int* nums, int numsSize) {
    int low = 0,step = numsSize - 1;
    while(step)
    {
        while(low + step >= numsSize||nums[low] > nums[low + step])
            step >>= 1;
        low += step;
    }
    return nums[(low+1)%numsSize];
}


Post a Comment

0 Comments