81. 搜索旋转排序数组 II

题意

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了

旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ...,

nums[k-1]]（下标 从 0 开始 计数）。

例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是

否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false

。

你必须尽可能减少整个操作步骤。

难度

中等

示例

示例 1：

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

输出：true

示例 2：

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

输出：false

分析

本题相较于 033.搜索旋转排序数列 来说，最大的不同在于 033.搜索旋转排序数列 是明确

的升序数列，而本题是未降序排列的数列，我们来咬文嚼字分析一下之间的差异。

升序和非降序是两个经常在算法和数据结构中使用的术语，它们的定义如下：

1. 升序 (Ascending Order)：

– 当一个序列的任何两个相邻的元素都满足：a[i] < a[i+1] 时，该序列被称为

升序。

– 换句话说，每一个元素都比它前面的元素大。

– 例如：[1, 2, 3, 4, 5] 是升序。

2. 非降序 (Non-descending Order)：

– 当一个序列的任何两个相邻的元素都满足：a[i] <= a[i+1] 时，该序列被称为

非降序。

 – 换句话说，每一个元素都大于或等于它前面的元素。

– 非降序包括了升序和部分元素相等的情况。

– 例如：[1, 2, 2, 3, 4, 5] 是非降序，但不是纯升序。

这下就明白了吧，就是所有升序的序列都是非降序的，但并非所有非降序的序列都是升序

的，里面存在一些元素相等的情况。

也就是说 033.搜索旋转排序数列 不存在重复的元素，而本题可能存在。

回想一下我们在处理 033.搜索旋转排序数列 时是怎么做的。

我们用了 二分查找。

二分查找的基本原理是每次比较数组的中间值和目标值。如果它们相等，我们找到了目

标；否则，我们将查找范围减半。

在一个标准的升序数组中，二分查找很简单。但这里的数组是一个非降序数组的旋转，所

以可能有两个非降序的子序列。

观察题目中给出的例子：[0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为

[4,5,6,6,7,0,1,2,4,4]。

如果我们在下标 5 的地方切开，也就是说，我们将数组分成了 [4,5,6,6,7] 和 [0,1,2,4,4]

两个子序列，其中前一个子序列是非降序的，后一个子序列也是非降序的。并且前一个子

序列的任意元素都大于或者等于后一个子序列的任意元素。

这启示我们可以继续使用二分查找：如果 target 位于子序列，我们可以对这个子序列继

续二分查找，否则我们对另一个子序列继续二分查找。

现在唯一的麻烦是本题存在重复的元素，会出现 nums[lef] == nums[mid] ==

nums[rig]的情况。

考虑数组 [2, 2, 2, 2, 4, 2, 2]，这是一个由 [2, 2, 2, 2, 2, 2, 4] 旋转得到的数组。假设目

标值 target = 4。

首先，定义 lef = 0 和 rig = 6。

第一步：

• lef = 0, rig = 6, mid = (0 + 6) / 2 = 3，所以 nums[mid] = 2。

• nums[lef] = 2，nums[rig] = 2

此时，我们注意到 nums[lef] == nums[mid] == nums[rig]。

但如果 nums[lef] == nums[mid] == nums[rig]，我们将面临一个问题，即解可能在

mid 的左边或右边，我们不能确定。

既然不能确定，索性我们将 lef 向右移动一位，将 rig 向左移动一位，来跳过重复的元

素，这样我们就可以继续在缩小的范围内查找目标。

解决了这个麻烦，接下来我们需要确定中间值是在左段还是右段。

• 如果 nums[lef] <= nums[mid]，那么中间值在左段（升序的）。然后我们检查目标

值是在左段还是右段，并相应地调整 lef 或 rig。

• 如果中间值在右段，处理方式与上述类似。

为什么这样就可以确定中间值在左段还是右段呢？

因为旋转排序数组存在这样一个特点：左段的所有值都大于等于首值，且都大于右段的任

意值；右段的所有值都小于等于尾值，且都小于左段的任意值。比如说：

[4,5,6,6,7,0,1,2,4,4]，左段为[4,5,6,6,7]，右段为[0,1,2,4,4]。

所以，对于数组的中间值：

1. 如果 **nums[mid] >= nums[lef]**，则 mid 位于左段。

– 如果数组没有旋转（例如 [1,2,3,4,5]），中间值当然是大于等于首值的。

– 如果数组旋转了（例如 [4,5,6,1,2,3]），mid 为 6 在左段，它仍然是大于等于

首值的。

2. 如果 **nums[mid] <= nums[rig]**，则 mid 位于右段。同样的逻辑，考虑两种情

况：

– 如果数组没有旋转，中间值当然是小于等于尾值的。

– 如果数组旋转了，并且 mid 在右段，它肯定是小于等于尾值的，例如

[2,5,6,0,0,1,2]。

通过上述方法，我们可以很容易地判断中间值是在左段还是右段。

好了，确定好左段还是右段，就是在子序列中进行二分查找了：

• 如果[lef,mid - 1]是非降序的，而且 nums[lef] <= target && target <

nums[mid]，那么答案肯定存在于[lef, mid - 1]中，调整上界 rig 到 mid - 1。

• 如果[mid，rig]是有序的，而且 nums[mid] < target && target <= nums[rig]，那

么答案肯定存在于[mid,rig]中，调整下界 lef 到 mid 即可。

代码方面也与 033.搜索旋转排序数列 大差不差，只是增加了对于 nums[lef] ==

nums[mid] == nums[rig]情况的处理。

class Solution {

public boolean search(int[] nums, int target) {

int n = nums.length; // 获取数组长度

// 若数组只有一个元素，直接对比目标值

if(n == 1) {

return nums[0] == target;

}

// 若数组为空，直接返回 false

if(n == 0)

return false;

// 定义左右指针，用于二分查找

int lef = 0, rig = n - 1;

 // 进行二分查找

while(lef <= rig) {

int mid = (lef + rig) >> 1; // 计算中间位置

if(nums[mid] == target) // 目标找到，返回 true

return true;

// 当左、中、右指针的值都相等时，无法确定该向哪边收缩，所以两边都收缩

if(nums[lef] == nums[mid] && nums[mid] == nums[rig]) {

++lef;

--rig;

} else {

// 中间值在左段（左段是升序的）

if (nums[lef] <= nums[mid]) {

if (nums[lef] <= target && target < nums[mid]) { // target 在左段中

rig = mid - 1;

} else { // target 在右段中

lef = mid + 1;

}

} else { // 中间值在右段（右段是升序的）

if (nums[mid] < target && target <= nums[n - 1]) { // target 在右段中

lef = mid + 1;

} else { // target 在左段中

rig = mid - 1;

}

}

}

}

return false; // 未找到目标值

}

}

我们来演变一下。

假设我们要查找 target = 6 是否在数组 [4,5,6,6,7,0,1,2,4,4] 中。

首先，初始化下标：

lef = 0

rig = 9

数组长度 n = 10

在循环开始时，我们计算中间位置的索引：

mid = (lef + rig) / 2 = (0 + 9) / 2 = 4

nums[mid] = 7

我们来检查三个关键位置的值：

nums[lef] = 4

nums[mid] = 7

nums[rig] = 4

在第一次循环时，nums[lef]=nums[rig] 但不等于 nums[mid]。

我们知道 mid 点在左半段（升序段）因为 nums[lef] <= nums[mid]。

接下来我们检查 target 是否在这个左段中。因为 nums[lef] <= target 且 target <

nums[mid] 成立，所以我们知道目标在左半部分。

因此，我们更新：

rig = mid - 1 = 3

缩小范围后，进入第二次循环，计算新的中间位置：

mid = (0 + 3) / 2 = 1

nums[mid] = 5

此时：

• nums[lef] = 4

• nums[mid] = 5

• nums[rig] = 6

• target = 6

• let = 0

• rig = 3

• mid = 1

nums[lef] 小于 nums[mid]，所以我们知道中间值 mid 在子序列的左半段（[4,5]）。

nums[lef] 小于 target 但 target 不小于 nums[mid]，所以 target 在右段（[6,6]）。

因此，我们更新：

lef = mid + 1 = 2

进一步缩小范围，此时 rig = 3，继续第三次循环，计算新的中间位置：

mid = (2 + 3) / 2 = 2

好，找到 nums[mid] = 6 = target 了，返回 true。

来看一下运行效率：

081.%E6%90%9C%E7%B4%A2%E6%97%8B%E8%BD%AC%E6%8E%92%E5%BA%8F%E

6%95%B0%E7%BB%84II-20230927083106.png

总结

本题仍然是对过去知识的简单变形（二分查找法），麻烦点在于可能会出现 lef,mid,rig

三者相等的情况，这时候该如何跳出这个困境？答案是去掉重复元素就行了。

力扣链接：https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/

更新: 2023-09-27 02:44:45

原文: https://www.yuque.com/itwanger/czfoq9/gmmv4r