81.md

题目地址

https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/

解答1

class Solution:
    RUN = True

    def search(self, nums: List[int], target: int) -> bool:
        """
            搜索旋转排序数组II

            假设按照升序排序的数组在预先未知的某个点上进行了旋转。
            ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
            编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
        """
        i, j = 0, len(nums) - 1
        if nums and self.RUN:
            in_middle = (j + i) // 2
            list1 = nums[:in_middle + 1]
            list2 = nums[in_middle + 1:]
            if nums[in_middle] > nums[i]:
                res = self.binarySearch(list1, target)
                if res == -1:
                    return self.search(list2, target)
                else:
                    return True
            elif nums[in_middle] == nums[i]:
                if nums[i] == target:
                    return True
                elif list1.count(nums[i]) == len(list1):
                    return self.search(list2, target)
                else:
                    return self.search(list1, target)
            else:
                res = self.binarySearch(list2, target)
                if res == -1:
                    return self.search(list1, target)
                else:
                    return True

        if not self.RUN:
            return True
        return False

    def binarySearch(self, nums, target):
        """ 二分查找 """
        i, j = 0, len(nums) - 1
        while i <= j:
            in_middle = (j + i) // 2
            if nums[in_middle] == target:
                self.RUN = False
                return in_middle
            elif nums[in_middle] < target:
                i = in_middle + 1
            else:
                j = in_middle - 1

        return -1

解答2

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        """
            搜索旋转排序数组II(非最优解)

            假设按照升序排序的数组在预先未知的某个点上进行了旋转。
            ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
            编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
        """
        if not nums:
            return False
        low = 0
        high = len(nums) - 1
        while low <= high:
            while low < high and nums[low] == nums[high]:  # 这样的目的是为了能准确判断mid位置，所以算法的最坏时间复杂度为O(n)
                low += 1
            mid = (low + high) // 2
            if target == nums[mid]:
                return True
            elif nums[mid] >= nums[low]:  # 高区
                if nums[low] <= target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            elif nums[mid] <= nums[high]:  # 低区
                if nums[mid] < target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1
        return False