153. Find Minimum in Rotated Sorted Array

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number}
 */

题目给我们一个升序排序后向右旋转 n 位的数字数组 nums

要求我们在 O(log n) 的事件复杂度内找出数组最小的元素

解题思路

一看到 log n 就知道需要使用二分搜索了

这题有点像 33. Search in Rotated Sorted Array 我们可以用类似思路来求解：

• 如果 nums[mid] > nums[left] 代表 mid 的左边是升序排列
• 如果 nums[mid] < nums[right] 代表 mid 的右边是升序排列

此外，我们需要一个变量 min 来记录当前遇到的最小元素，并在每次赋值前比较

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let left = 0
    let right = nums.length - 1
    let min = Number.MAX_SAFE_INTEGER

    while(left <= right) {
        const mid = Math.floor((left + right) / 2)
        min = Math.min(nums[mid], min)

        if(nums[mid] < nums[right]) {
            // right side of mid is ascending
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return min
};