【月度刷题计划同款】详解为何元素相同会导致 O(n)，一起看清二分的本质

题目描述

这是 LeetCode 上的「81. 搜索旋转排序数组 II」，难度为「中等」。

Tag : 「二分」

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

代码语言：javascript复制

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

输出：true

示例 2：

代码语言：javascript复制

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

输出：false

提示：

1 <= nums.length <= 5000

-10^4 <= nums[i] <= 10^4

• 题目数据保证 nums 在预先未知的某个下标上进行了旋转

-10^4 <= target <= 10^4

二分

根据题意，我们知道，所谓的旋转其实就是「将某个下标前面的所有数整体移到后面，使得数组从整体有序变为分段有序」。

但和 33. 搜索旋转排序数组 不同的是，本题元素并不唯一。

这意味着我们无法直接根据与

nums[0]

的大小关系，将数组划分为两段，即无法通过「二分」来找到旋转点。

因为「二分」的本质是二段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。

如果你有看过我 33. 搜索旋转排序数组 这篇题解，你应该很容易就理解上句话的意思。如果没有也没关系，我们可以先解决本题，在理解后你再去做 33. 搜索旋转排序数组，我认为这两题都是一样的，不存在先后关系。

举个