前往此题

解题思路

按照例题可以把该数组拆为2个区间。

第一种情况：

[2,5,6,0,0,1,2]拆解为[2,5,6]和[0,0,1,2]。

这种情况这两个区间都是升序的，在查找过程中只要确定target在哪个区间内就能通过二分查找直接锁定

第二种情况

[3,2,0,1,2] 拆解为 [3,2] 和 [0,1,2]

这种前者肯定是无序的，后者是有序的情况下（包括重复元素）。所以后者的判断条件如果写成nums[left] < nums[mid]的时候需要考虑到重复元素的情况，否则如[0,0,1]会出错。

第三种情况
最后一种情况[1,1,1,0,1]拆解为[1,1,1,1]和[0] 以及 [3,1]都无法确定是否有序。
这里特殊情况也要考虑进去, 通过left = left + 1来过滤掉重复项。

代码

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        size = len(nums)
        if size == 0: return False

        left, right = 0, size - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[left]:
                if nums[left] <= target <= nums[mid]: right = mid
                else: left = mid + 1
            elif nums[mid] < nums[left]:
                if nums[mid] < target <= nums[right]: left = mid + 1
                else: right = mid
            else:
                if nums[left] == target: return True
                left = left + 1
        return nums[left] == target