【LeetCode】搜索旋转排序数组[python]

整数数组nums按升序排序，数组中的值互不相同，在传递给函数之前，nums在预先未知的某个下标k上进行了旋转，使数组变为[nums[k],nums[k+1],...,nums[n-1],nums[0],...,nums[k-1]](下标从0开始)。例如[0,1,2,3,4,5,6,7]经下标3处旋转为[4,5,6,7,0,1,2]。

给你旋转后的数组nums和一个整数target，如果nums中存在这个目标值target，返回它的下标，否则返回-1.

eg：输入nums=[4,5,6,7,0,1,2],target=0,输出4.

解题思路：此题基于二分查找，判断中值左右两边序列是否为有序数列（此题为有序数列旋转后，则中值前后必为一段有序数列，且为升序）。故中值与边界值比较大小即可。中值大于左边界值，则左边为有序数列，反之中值小于右边界值。则右边为有序数列。再去判断目标值是否在有序数列中，存在则将中值替换为有序数列边界值，反之替换为无序数列边界值。

class Solution(object):
    def search(self,nums,target):
        l=-1   #基于二分查找，模板，定义左边边界
        r=len(nums)  #定义右边边界
        if len(nums)==1:
            if target==nums[0]:
                return 0
            else:return -1
        while l+1!=r:   #循环判断是否只剩唯一中值
            m=int((l+r//2))
            a = nums[m]
            if a==target:  #中值与目标值进行判断
                return m
            elif a>nums[l]: #中值与目标值不等时，如果中值大于目标边界，说明左边序列有序
                if target<a and target>nums[l]: #再去判断目标值是在[左边界，中值]
                    r=m
                else: l=m
            elif a<nums[r-1]:
                if target>a and target<=nums[r-1]:
                    l=m
                else: r=m
            else:return -1
        return -1