# 5.搜索旋转排序数组(middle)

TIP

更好的阅读体验应该是:

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

# 一、题目

LeetCode:33.搜索旋转排序数组 (opens new window)

给你一个整数数组 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 search = function(nums, target) {
    // 定义[left, right] 边界
    let left = 0;
    let right = nums.length - 1;
    // [0, 1]
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] === target) return mid;
        // 如果左侧为升序排列
        if (nums[mid] >= nums[left]) {
            if (target >= nums[left] && target < nums[mid]) {
                // 如果目标元素在升序排列中
                right = mid - 1; // 忽略右侧排列
            } else {
                left = mid + 1; // 忽略左侧排列
            }
        } else {
            // 如果右侧为升序排列
            if (target <= nums[right] && target > nums[mid]) {
                left = mid + 1; // 忽略左侧排列
            } else {
                right = mid - 1; // 忽略右侧排列
            }
        }
    }
    return -1;
};

# 三、写在最后

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

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

关于我

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

其他沉淀

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