33.md

题目地址

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

解答

class Solution:
    TOTAL = 0
    RUN = True

    def search(self, nums, target):
        """ 搜索旋转排序数组 """
        # 将数组一分为二，分别比头尾，尾大于头为有序，剩下的为无序
        i, j = 0, len(nums) - 1
        res = -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:
                    self.TOTAL += in_middle + 1
                    self.search(list2, target)
                else:
                    self.TOTAL += res
            else:
                res = self.binarySearch(list2, target)
                if res == -1:
                    self.search(list1, target)
                else:
                    self.TOTAL += in_middle + 1 + res

        if not self.RUN:
            return self.TOTAL
        return res

    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