Find Minimum in Rotated Sorted Array

Problem

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.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let lo = 0;
    let hi = nums.length - 1;
    while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (nums[lo] > nums[mid]) { // min value (ie. pivot) in [lo, mid]
            hi = mid;
        } else if (nums[mid] > nums[hi]) { // min value (ie. pivot) in [mid + 1, hi]
            lo = mid + 1;
        } else { // min value (ie. pivot) is lo
            break;
        }
    }
    return nums[lo];
};

Essentially, to find the min value, we must find the pivot location of nums. We can do this using binary search by continuously iterating on the half that is not sorted (ie. if nums[lo] > nums[mid] => [lo, mid] is not sorted, and if nums[mid] > nums[hi] => [mid + 1, hi] is not sorted). When both halves [lo, mid] and [mid, hi] are sorted, we know the min/pivot is at index lo.

For example, if nums = [3, 4, 5, 1, 2], we get nums[mid] = 5, where the half [5, 1, 2] is not sorted; so we iterate on [5, 1, 2]. In the next iteration, we get nums[mid] = 1, where the half [5, 1] is not sorted; so we iterate on [1]. Since the subarray is now sorted, we break and return nums[lo] = 1.

Problem​

Solution​

Problem

Solution