Leetcode 153 Find Minimum in Rotated Sorted Array

Leetcode 153 Find Minimum in Rotated Sorted Array

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description

Obviously this problem can be solved by looping through the array once and find the first element that’s smaller then the previous one. Easy!

But we are actually asked to solve it in O(log n) time.

As soon as I see O(log n), binary search jumps into my mind. But how do we move the middle pointer at each iteration?

Let’s take the following rotated array as an example:

[ 3, 4, 5, 1, 2]

If the middle pointer falls into the left side of the smallest number, all the elements are greater or equal than the first element 3, we should move the left point to the middle pointer. If if falls into the right side, all the elements are less than the first element 3 and we should move the right pointer to mid.

Looks like we have a solution by comparing the middle point element and the first element.

Let’s take a look at the solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let left = 0;
    let right = nums.length - 1;
    while(left + 1 < right) {
        const mid = Math.floor((left + right) / 2);
        if(nums[mid] > nums[0]) {
            left = mid
        } else {
            right = mid
        }
    }
    
    return Math.min(nums[left], nums[right], nums[0])
};

One thing to note is when we are out of the while loop and find the min number, we need to include the first element in the array as well. Because after n rotations, the array will go back to its original form. Now the left pointer will keep going to the end of the array. So we need to include the first element to the comparison as well.