081.搜索旋转排序数组II

作者：沉默王二
发布时间：2023-09-27T10:47:07.115+0800

---

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

已知存在一个按非降序排列的整数数组 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

示例 2：

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

分析

本题相较于 033.搜索旋转排序数列 来说，最大的不同在于 033.搜索旋转排序数列 是明确的升序数列，而本题是未降序排列的数列，我们来咬文嚼字分析一下之间的差异。

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

• 升序 (Ascending Order)：
• 当一个序列的任何两个相邻的元素都满足：a[i] < a[i+1] 时，该序列被称为升序。
• 换句话说，每一个元素都比它前面的元素大。
• 例如：[1, 2, 3, 4, 5] 是升序。
• 非降序 (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]。

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

• 如果 nums[mid] >= nums[lef]，则 mid 位于左段。
• 如果数组没有旋转（例如 [1,2,3,4,5]），中间值当然是大于等于首值的。
• 如果数组旋转了（例如 [4,5,6,1,2,3]），mid 为 6 在左段，它仍然是大于等于首值的。
• 如果 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 {

        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。

来看一下运行效率：

总结

本题仍然是对过去知识的简单变形（二分查找法），麻烦点在于可能会出现lef,mid,rig三者相等的情况，这时候该如何跳出这个困境？答案是去掉重复元素就行了。

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

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

已知存在一个按非降序排列的整数数组 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

示例 2：

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

分析

本题相较于 033.搜索旋转排序数列 来说，最大的不同在于 033.搜索旋转排序数列 是明确的升序数列，而本题是未降序排列的数列，我们来咬文嚼字分析一下之间的差异。

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

• 升序 (Ascending Order)：
• 当一个序列的任何两个相邻的元素都满足：a[i] < a[i+1] 时，该序列被称为升序。
• 换句话说，每一个元素都比它前面的元素大。
• 例如：[1, 2, 3, 4, 5] 是升序。
• 非降序 (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]。

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

• 如果 nums[mid] >= nums[lef]，则 mid 位于左段。
• 如果数组没有旋转（例如 [1,2,3,4,5]），中间值当然是大于等于首值的。
• 如果数组旋转了（例如 [4,5,6,1,2,3]），mid 为 6 在左段，它仍然是大于等于首值的。
• 如果 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 {

        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。

来看一下运行效率：

总结

本题仍然是对过去知识的简单变形（二分查找法），麻烦点在于可能会出现lef,mid,rig三者相等的情况，这时候该如何跳出这个困境？答案是去掉重复元素就行了。

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

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

已知存在一个按非降序排列的整数数组 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

示例 2：

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

分析

本题相较于 033.搜索旋转排序数列 来说，最大的不同在于 033.搜索旋转排序数列 是明确的升序数列，而本题是未降序排列的数列，我们来咬文嚼字分析一下之间的差异。

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

• 升序 (Ascending Order)：
• 当一个序列的任何两个相邻的元素都满足：a[i] < a[i+1] 时，该序列被称为升序。
• 换句话说，每一个元素都比它前面的元素大。
• 例如：[1, 2, 3, 4, 5] 是升序。
• 非降序 (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]。

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

• 如果 nums[mid] >= nums[lef]，则 mid 位于左段。
• 如果数组没有旋转（例如 [1,2,3,4,5]），中间值当然是大于等于首值的。
• 如果数组旋转了（例如 [4,5,6,1,2,3]），mid 为 6 在左段，它仍然是大于等于首值的。
• 如果 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 {

        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。

来看一下运行效率：

总结

本题仍然是对过去知识的简单变形（二分查找法），麻烦点在于可能会出现lef,mid,rig三者相等的情况，这时候该如何跳出这个困境？答案是去掉重复元素就行了。

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

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412