# 3.寻找旋转排序数组中的最小值（middle）

TIP

更好的阅读体验应该是：

  1. 审题-思考
  2. 答题
  3. 整理-归纳

# 一、题目

153. 寻找旋转排序数组中的最小值 (opens new window)

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组  [0,1,2,4,5,6,7] 可能变为  [4,5,6,7,0,1,2] 。

请找出其中最小的元素。

示例

输入：nums = [4,5,6,7,0,1,2]
输出：0

注意

  • nums 中的所有整数都是 唯一 的
  • nums 原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转
  • 最终目的是找到拐点，因为一个递增序列的旋转，拐点即最小

# 二、基础模版 II

  1. 确定初始的左右边界:
    • left: 0
    • right: nums.length-1
    • mid: (left + (right - left) >> 1)
  2. 查找条件需要访问元素的直接右邻居。
  3. 使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
  4. 保证查找空间在每一步中至少有 2 个元素。
  5. 需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

# 三、题解

Javasciprt 代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    let mid = left + ((right - left) >> 1);
    // 与nums[right]比较是因为，是递增序列
    if (nums[mid] > nums[right]) {
      // 中间值 > 末尾 = 证明拐点在右侧，递增区间在左侧，不用看左侧了
      left = mid + 1;
    } else {
      right = mid;
      // 中间值 < 末尾 = 右侧是递增序列，右侧较大的区间可以忽略
    }
  }
  return nums[left];
};

# 四、写在最后

本文是二分查找-模版 II 的最后一题，接下来我们将面对更大的挑战，加油～

如果对你有所帮助不妨给本项目的github 点个 star (opens new window)，这是对我最大的鼓励

关于我

  • 花名：余光
  • WX：j565017805
  • 沉迷 JS，水平有限，虚心学习中

其他沉淀

Last Updated: 8/6/2021, 6:58:15 PM