33. Search in Rotated Sorted Array
python
class Solution:
def search(self, nums: List[int], target: int) -> int:
def bisearch(l, r, target):
while l <= r:
mid = (l + r) // 2
v = nums[mid]
if v < target:
l = mid + 1
else:
r = mid - 1
if l == n:
return -1
if nums[l] != target:
return -1
return l
n = len(nums)
left, right = 0, n-2
while left <= right:
mid = (left + right) // 2
v = nums[mid]
if v < nums[-1]:
right = mid-1
else:
left = mid + 1
min_num_i = left
if nums[-1] < target:
# 在左半边
return bisearch(0, min_num_i, target)
elif nums[-1] > target:
return bisearch(min_num_i, len(nums)-1, target)
else:
return n-1两次二分：
找到旋转数组中的最小值
python
n = len(nums)
left, right = 0, n-2
while left <= right:
mid = (left + right) // 2
v = nums[mid]
if v < nums[-1]:
right = mid-1
else:
left = mid + 1
min_num_i = left找到第一个>= target的数
python
def bisearch(l, r, target):
while l <= r:
mid = (l + r) // 2
v = nums[mid]
if v < target:
l = mid + 1
else:
r = mid - 1
if l == n:
return -1
if nums[l] != target:
return -1
return l和最后一个数比较，判断target在哪一个区域，对该区域应用二分
python
min_num_i = left
if nums[-1] < target:
# 在左半边
return bisearch(0, min_num_i, target)
elif nums[-1] > target:
return bisearch(min_num_i, len(nums)-1, target)
else:
return n-1