2022-2023-1 数据结构 期末压轴题回忆

https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/solutions/705486/gong-shui-san-xie-xiang-jie-wei-he-yuan-xtam4/

二分解法

根据题意，我们知道，所谓的旋转其实就是「将某个下标前面的所有数整体移到后面，使得数组从整体有序变为分段有序」。 但和 33. 搜索旋转排序数组 不同的是，本题元素并不唯一。 这意味着我们无法直接根据与 nums[0] 的大小关系，将数组划分为两段，即无法通过「二分」来找到旋转点。 因为「二分」的本质是二段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。

如果你有看过我 【宫水三叶】严格 O(logN)，一起看清二分的本质 这篇题解（https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/shua-chuan-lc-yan-ge-ologn100yi-qi-kan-q-xifo/），你应该很容易就理解上句话的意思。如果没有也没关系，我们可以先解决本题，在理解后你再去做 33. 搜索旋转排序数组（https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/），我认为这两题都是一样的，不存在先后关系。

举个🌰，我们使用数据 [0,1,2,2,2,3,4,5] 来理解为什么不同的旋转点会导致「二段性丢失」：

时间复杂度：恢复二段性处理中，最坏的情况下（考虑整个数组都是同一个数）复杂度是 O(n)，而之后的找旋转点和目标值都是「二分」，复杂度为 O(logn)。整体复杂度为 O(n) 的。 空间复杂度：O(1)

22级期末一道有争议的题