33. Search in Rotated Sorted Array
程序员文章站
2022-07-15 19:45:09
...
https://leetcode.com/problems/search-in-rotated-sorted-array/description/
题意:给一个升序数组从中间翻转后的数组,还有一个target,用logn的复杂度搜索这个target,返回其下标,否则-1
思路:
如下图
由于是翻转数组,且无重复,因此nums[0]必然大于nums[n-1](为什么?写出来就知道),所有的数分成两支,每支内依然升序。问题是不知道断点在哪。
因此可以先取mid,看target与mid是否在同一支上,若在同一支,可以直接在该支上做二分查找。
若不在同一支,例如mid在左,tar在右,则mid往右收缩;反之则mid往左收缩
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
n = len(nums)
lo, hi = 0, n-1
while lo <= hi: #二分查找
mid = (lo + hi) // 2
if target > nums[0]: #target在左分支
if nums[mid] >= nums[0]: #mid也在左分支
tmp = nums[mid]
else:
tmp = float('inf')
elif target == nums[0]: #恰好等于左端点
return 0
elif target == nums[n-1]: #恰好等于右端点
return n-1
else: #target在右分支
if nums[mid] < nums[0]:
tmp = nums[mid]
else:
tmp = -float('inf')
#二分,用tmp而不是mid与tar比较
if tmp < target:
lo = mid + 1
elif tmp > target:
hi = mid - 1
else:
return mid
return -1
推荐阅读
-
Convert Sorted Array to Binary Search Tree
-
LeetCode 33. Search in Rotated Sorted Array && 81. Search in Rotated Sorted Array II
-
Leetcode 33 Search in Rotated Sorted Array
-
LeetCode·33. Search in Rotated Sorted Array
-
leetcode 33. Search in Rotated Sorted Array
-
0033_Search in Rotated Sorted Array
-
Search in Rotated Sorted Array II
-
33. Search in Rotated Sorted Array
-
LeetCode------Search in Rotated Sorted Array
-
33. Search in Rotated Sorted Array