13. 搜索旋转排序数组.md

整数数组 nums 按升序排列，数组中的值互不相同 。给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        #二分法找到数组中的最小值及其索引
        i, j = 0, len(nums)-1
        while i<=j:
            m = (i+j)//2
            if nums[m] > nums[j]:
                i = m+1
            elif nums[m] < nums[j]:
                j = m
            else:
                j -= 1
        min_ind, min_num = i, nums[i]
        #构造函数找到升序数组中某个特定值的索引
        def bsearch(nums, target):
            low = 0
            high = len(nums) - 1
            while low <= high:
                mid = (low+high)//2
                if nums[mid] > target:
                    high = mid-1
                elif nums[mid] < target:
                    low = mid + 1
                else:
                    return mid
            return -1
        #边界情况处理
        if min_ind == 0:
            return bsearch(nums, target)
        else:
            if nums[0] == target:
                return 0
            elif nums[0] < target:
                return bsearch(nums[:min_ind], target)
            else:
                ind = bsearch(nums[min_ind:], target)
                if ind != -1:
                    return ind+min_ind
                else:
                    return -1