LeetCode题解：搜索旋转排序数组

搜索旋转排序数组（middle）

更好的阅读体验应该是：

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

一、题目

LeetCode：33.搜索旋转排序数组

给你一个整数数组 nums ，和一个整数 target 。

该整数数组原本是按升序排列，但输入时在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。

请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

示例 1：

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

二、二分法解题

二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

• 如果目标值等于中间元素，则找到目标值。
• 如果目标值较小，继续在左侧搜索。
• 如果目标值较大，则继续在右侧搜索。

分析模版

1. 确定
   • left = 0;
   • right = nums.length - 1;
   • mid = left + ((right - left) >> 1);
2. 终止搜索条件为 left <= right。
3. 判断中间值是在有序区间内还是在无序区间内(因为只有1个转折点)
   • nums[mid] > nums[left]，则 mid 在左侧升序区间
   • nums[mid] < nums[left]，则 mid 在右侧升序区间
4. 继续判断 target 与有序区间的边界进行比较
   • 确定 mid 在左侧升序区间，target 与左区间（[left, mid]）的最大值比较，即 target <= nums[mid] && target >= nums[left] 时，target 在左侧区间，可以直接舍弃右侧部分，反之则舍弃左侧部分
   • 确定 mid 在右侧升序区间，target 与右区间（[mid, right]）的最小值比较，即 target >= nums[mid] && target <=> nums[right] 时，target 在右侧区间，可以直接舍弃左侧部分，反之则舍弃右侧部分

Javasciprt 代码

var guessNumber = function(n) {
  let left = 0; // 初始左边界
  let right = n; // 初始右边界
  while (left <= right) {
    var mid = left + Math.floor((right - left) / 2); //防止溢出
    if (guess(mid) === 0) {
      return mid;
    } else if (guess(mid) === 1) {
      // 目标值大于中值，则中间左侧可以抛弃了
      left = mid + 1;
    } else {
      // 目标值小于中值，则中间右侧可以抛弃了
      right = mid - 1;
    }
  }
  return -1;
};

三、写在最后

本文是二分查找-模版 I 的最后一题，你会发现这道题的难度确实提升了，但仔细分析，借助自己的写写画画，仍然可以找到模版I的影子，加油！

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

关于我

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

其他沉淀

• JavaScript 版 LeetCode 题解
• 前端进阶笔记
• CSDN

本文地址：https://blog.csdn.net/jbj6568839z/article/details/111029022