LeetCode 81，在不满足二分的数组内使用二分法 II

本文始发于个人公众号：TechFlow，原创不易，求个关注

今天是LeetCode专题第50篇文章，我们来聊聊LeetCode中的81题Search in Rotated Sorted ArrayII。

它的官方难度是Medium，点赞1251，反对470，通过率32.8%。从通过率上来看，这题属于Medium难度当中偏难一些的题目，也的确如此，稍稍有些考验思维。

题意

假设我们有一个含有重复元素的有序数组，我们随意选择一个位置将它分成两半，然后将这两个部分调换顺序拼接成一个新的数组。现在给定一个target，要求返回一个bool结果，表明target是否在数组当中。

样例

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

如果是你按照顺序刷LeetCode或者是本专题的话，你会发现我们在之前做过一道非常相似的题目。它就是LeetCode的33题，Search in Rotated Sorted ArrayI。不过不同的是，在33题的题意当中，明确表明了数组当中的元素是不包含重复元素的，除此之外，这两题的题意完全一样。

LeetCode 33，在不满足二分的数组内使用二分的方法

这么一点小小的差别会带来解法的变化吗？

题解

答案当然是肯定的，不然出题人可以退休了。

问题是，问题出在哪里呢？

我们先不着急，先来回忆一下33题中的做法。我们当时使用了一个最简单的笨办法，就是先通过二分法找到数组截断的位置。然后再通过截断的位置还原出原数组的情况，根据我们target的大小，找到它可能存在的位置。

但是在当前这个问题当中，这个思路走不通了。走不通的原因也很简单，就是因为重复元素的存在。

举个例子：[1, 3, 1, 1, 1, 1, 1, 1]

当我们进行二分查找的时候，发现mid是1和left的1相等，我们根本无法判断截断点究竟在mid的左侧还是右侧，二分查找也就无从谈起了。

我们当然可以退一步采用遍历的方法去寻找切分点，但是既然如此，我们为什么不直接去寻找答案呢？反正都已经是O(n)的复杂度了。所以这是行不通的，我们想要使得复杂度维持在就必须要寻找其他的路数。

思路和解法很多时候不是凭空来的，需要我们对问题进行深入的分析。在这个问题当中，我们的问题是明确并且简单的。就是一个调换了部分顺序的有序数组，只是我们不确定的是调换的部分究竟有多长。由于我们最终希望通过二分法来寻找答案，所以我们可以根据调换的元素是否过半想出两种情况来。

我把这两种情况用图展示出来：

也就是说我们的分割点可能在数组的前半段也可能在后半段，对于这两种情况我们的处理方法是不同的。

我们先看第一种情况，数组的前半段是有序的，后半段存在截断。如果target的范围在前半段当中，我们可以抛弃掉后半段，直接在前半段中进行二分。否则，我们需要舍弃前半段，在后半段当中重复这个过程。我们可以把后半段看成是一个全新的问题，也一样可以分成两种情况，类似于递归一样的往下执行即可。

再来看第二种情况，第二种情况的后半段和第一种情况的前半段是一样的，都是有序的元素，我们直接二分即可。它的前半段和第一种情况的后半段是一样的，我们没法判断，需要继续二分。

也就是说，我们只能在有序的数组进行二分，如果当前数组存在分段，不是整体有序的，那我们就对它进行拆分。拆分之后总能找到有序的部分，如果还找不到就继续拆分。因为分段点只有一个，所以不论当前的数组什么样，拆分一次之后，必然至少可以找到一段是有序的。

想明白这点之后就简单了，看起来很像是递归，但实际上它的本质仍然是二分。代码并不难写，但是还有一个问题没解决，就是当nums[m] = nums[l]的时候，我们如何判断是哪一种情况呢？

答案是没法判断，两种情况都有可能，对于这种情况也没有很好的办法，我想出来的办法是可以将l向右移动一位，相当于抛弃了一个最左侧的数。我们把这些思路总结总结，代码也就出来了：

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        l, r = 0, len(nums)-1
        while l <= r:
            m = (l + r) >> 1
            if nums[m] == target:
                return True
            
            if nums[l] == nums[m]:
                l += 1
                continue
                
            if nums[l] < nums[m]:
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            else:
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
        return False

总结

到这里，我们关于这道题的题解就结束了。在问题的最后，出题人给我们留了一个问题，和33题比起来，这题的解法的时间复杂度会有变化吗？

表面上看我们一样用到了二分，所以同样是log级的复杂度，问题的复杂度并没有变化。但实际上并不是这样的，我们来看一种最坏的情况，假设数组当中所有的值全部相等。这个时候二分就不起效果了，最终会退化成O(n)的线性枚举，这样又变成了O(n)的复杂度。当然，在大部分情况下，这并不会发生。所以是算法的最坏复杂度退化成了O(n)，平均复杂度依然是O(logN)。

如果喜欢本文，可以的话，请点个关注，给我一点鼓励，也方便获取更多文章。

本文使用 mdnice 排版