pythontip 100days-day17

Code › python
, ,

题目

升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为[4,5,6,7,0,1,2] ）。请你在数组中搜索target ，如果数组中存在这个目标值，则返回它的索引，否则返回-1。

例子

searchRotate([4,5,6,7,0,1,2],4) -> 0
searchRotate([4,5,6,7,0,1,2],3) -> -1
searchRotate([4,5,6,7,0,1,2],1) -> 5
searchRotate([1],0) -> -1

假设

  1. 输入数组不含重复元素

tips

  1. 二分查找变形

答案

解法1

def searchRotate(nums,target):
    if not nums:
        return -1
    i,j = 0,len(nums)-1
    while i <= j:
        m = (i + j) // 2
        if target == nums[m]:
            return m
        if nums[m] < target:
            if target >= nums[0] and nums[m] < nums[0]:
                j = m - 1
            else:
                i = m + 1
        else:
            if target <= nums[len(nums) - 1] and nums[m] > nums[len(nums) - 1]:
                i = m + 1
            else:
                j = m - 1
    return -1

性能：

  1. 时间复杂度O(logn)
  2. 空间复杂度O(1)

关键点：1.二分查找变形