JS Leetcode 81. 搜索旋转排序数组 II 题解，补救二分法的可行性

壹 ❀ 引

今日LeetCode题为153. 寻找旋转排序数组中的最小值，在10个月前，我已在JS leetcode 寻找旋转排序数组中的最小值 题解分析，你不得不了解的二分法一文中写了本题的题解，所以今日的题就不用再写博客记录了。而昨天的题81. 搜索旋转排序数组 II因为思路问题，我先记录了它的普通版33. 搜索旋转排序数组，所以按照约定，今天得把这道题的题解补回来，题目描述如下：

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

输出：true

输入：nums = [2,5,6,0,0,1,2], target = 3

输出：false

我们先来搜集题目信息，再开始实现它。（这篇文章本来应该昨天发，中午写了一半，晚上加班发版到凌晨1点半，苦不堪言….）

[0,1,1,1,1]

nums[0]target>=start&&targetmid&&target<=end

[1,0,1,1,1]mid>=nums[0]

[1,0]nums[0]

你也许会想，去除掉相同数字不会影响最终结果吗？但我们只是想在数组中找到目标元素，相同的元素本来存在一个就够了，如果数组不存在相同元素，那这题不就是昨天做的那道题了…而本题只是增加了重复元素故意作为了新的考点。

[1,0,1,1,1]

大家可以多列几个例子自行验证，所以这道题的解法，仅仅是在昨天那道题的代码基础上，做了一个当左右指针元素相等时修改指针的操作而已，代码如下：

/**



@param {number[]} nums

@param {number} target

@return {boolean}

*/

var search = function (nums, target) {

let l = 0;

let r = nums.length - 1;

while (l <= r) {

    const mid = Math.floor((l + r) / 2);

    // 如果mid就是目标值直接返回

    if (nums[mid] === target) {

        return true;

    };

    // 开始处理左右相同数字的情况

    if (nums[l] === nums[r]) {

        r–;

        // 继续判断还有没有相等的情况，直接跳过后续逻辑

        continue;

    };

    // 下面的逻辑与上一道题一模一样

    if (nums[mid] >= nums[l]) {

        //target 在 [l, mid] 之间

        if (target >= nums[l] && target < nums[mid]) {

            r = mid - 1;

        } else {

            //target 不在 [l, mid] 之间

            l = mid + 1;

        };

    } else {

        // [mid, r]有序

        // target 在 [mid, r] 之间

        if (target > nums[mid] && target <= nums[r]) {

            l = mid + 1;

        } else {

            // target 不在 [mid, r] 之间

            r = mid - 1;

        }

    }

}

return false;

};

所以这道题，只是增加了下面这一小段代码（你让l++也行）：

if (nums[l] === nums[r]) {

r–;// 或者l++都行，目的就是为了修复二分行，不让上面那种极端情况出现

continue;

};

而这一小段代码，就像是在不满足二分法情况下，再给程序一次机会一样，不会再修复二分特性，让程序能继续按照我们上道题的思路进行二分，从而判断出最终结果。