欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-24 16:45:44
搜索旋转排序数组(middle)更好的阅读体验应该是:审题-思考答题整理-归纳一、题目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,...

搜索旋转排序数组(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,水平有限,虚心学习中

其他沉淀

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

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