- 搜索旋转排序数组
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
测试用例:
nums =[4,5,6,7,0,1,2]
target =1
输出 -1
预期结果5
各位帮看看,这个测试用例为啥过不了,我手动一步步算,可以输出正常值
下面是我的代码,谢谢!
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
left = 0
right = n-1
# if n == 0:
# return -1
while left <= right:
mid = left + (right-left)//2
if nums[mid] == target:
return mid
if nums[mid] > nums[right]:
if nums[right] < target < nums[mid]:
right = mid - 1
else:
left = mid + 1
if nums[mid] <= nums[right]:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid -1
return left if nums[left] == target else -1