Skip to main content

寻找旋转排序数组中的最小值

题目​

已知一个长度为 n 的数组, 预先按照升序排列, 经由 1 到 n 次旋转后, 得到输入数组. 例如, 原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:

  • 若旋转 4 次, 则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次, 则可以得到 [0,1,2,4,5,6,7]

注意, 数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

给你一个元素值互不相同的数组 nums, 它原来是一个升序排列的数组, 并按上述情形进行了多次旋转. 请你找出并返回数组中的最小元素 .

你必须设计一个时间复杂度为 O(leftg n) 的算法解决此问题.

示例
输入: nums = [3,4,5,1,2]
输出: 1
解释: 原数组为 [1,2,3,4,5], 旋转 3 次得到输入数组.
输入: nums = [4,5,6,7,0,1,2]
输出: 0
解释: 原数组为 [0,1,2,4,5,6,7], 旋转 4 次得到输入数组.
输入: nums = [11,13,15,17]
输出: 11
解释: 原数组为 [11,13,15,17], 旋转 4 次得到输入数组.

题解​

比较 nums[mid] 和 nums[right]:

  • 如果 nums[mid] > nums[right], 则最小值一定在右半部分(不包括 mid), 令 left = mid + 1.
  • 如果 nums[mid] <= nums[right], 则最小值一定在左半部分(包括 mid), 令 right = mid.
  • 当循环结束时, left 和 right 相等, 它们指向的元素就是最小值.
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  let left = 0,
    right = nums.length - 1
  while (left < right) {
    const mid = Math.floor((left + right) / 2)

    if (nums[mid] > nums[right]) {
      left = mid + 1
    } else {
      right = mid
    }
  }
  return nums[left]
}