LeetCode题解：寻找旋转排序数组中的最小值

阳光穿透心脏的1/2处 2022-12-28 11:18 107阅读 0赞

# 模版 II-3 寻找旋转排序数组中的最小值（middle） #

> 更好的阅读体验应该是：
> 
> 1.  审题-思考
> 2.  答题
> 3.  整理-归纳  
>     :::

## 一、题目 ##

[153. 寻找旋转排序数组中的最小值][153.]

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 \[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 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

## 三、题解 ##

/** * @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][github _ star]，这是对我最大的鼓励

**关于我**

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

**其他沉淀**

*  [JavaScript 版 LeetCode 题解][JavaScript _ LeetCode]
 *  [前端进阶笔记][Link 1]
 *  [CSDN][]

![yuguang-csdn-bottom.gif][]

[153.]: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
[github _ star]: https://github.com/webbj97/summary
[JavaScript _ LeetCode]: https://webbj97.github.io/leetCode-Js/
[Link 1]: https://webbj97.github.io/summary/
[CSDN]: https://yuguang.blog.csdn.net/
[yuguang-csdn-bottom.gif]: /images/20221120/bfe74410011c4e59abe235d0cfef797b.png