【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 0else:return -1while l+1!=r:   #循环判断是否只剩唯一中值m=int((l+r//2))a = nums[m]if a==target:  #中值与目标值进行判断return melif a>nums[l]: #中值与目标值不等时，如果中值大于目标边界，说明左边序列有序if target<a and target>nums[l]: #再去判断目标值是在[左边界，中值]r=melse: l=melif a<nums[r-1]:if target>a and target<=nums[r-1]:l=melse: r=melse:return -1return -1