leetcode33 Search in Rotated Sorted Array

leetcode33 Search in Rotated Sorted Array


题目大意:
给定一个数组 数组是升序 但是可能旋转过 要求给定数字进行寻找 且时间复杂度 O(log n)
由于数组旋转过 不能使用普普通通的二分查找
但是可以根据每次的mid 跟与low与high进行比较 进行排除法
即:
如果mid 大于 low那么mid 到low 一定是升序 且如果target再里面 就把high 换成 mid -1 否则就把low设置为mid+1
如果 mid 小于high 那么后半部分一定是升序 同样判断是否符合条件

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
low,high=0,len(nums)-1
while low <= high:
mid = (low+high)//2
if nums[mid] == target:
return mid
if nums[low]<=nums[mid]: #前半部分是正常的升序
if nums[low] <=target < nums[mid]:
high = mid - 1
else:
low = mid + 1
else:#后半部分是正常的升序
if nums[mid] <=target<= nums[high]:
low = mid + 1
else:
high = mid -1
return -1