LeetCode 153. Find Minimum in Rotated Sorted Array (javascript solution)

#algorithms #javascript

Description:

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.

Solution:

Time Complexity : O(log(n))
Space Complexity: O(1)

// Binary Search 
var findMin = function(nums) {
    let left = 0, right = nums.length-1;
    while(left < right) {
        const mid = left + Math.floor((right-left)/2)
        // Move right pointer if num at mid is less than or equal to num at right. This means that the smallest number must be on the left side of mid including mid.
        if(nums[right] >= nums[mid]) {
            right = mid
        } else {
            left = mid+1
        }
    }
    return nums[left]
};