Leetcode算法——33、查询有序旋转数组
给定一个数组,这个数组是由一个升序数组进行左旋或右旋若干次得到的。
比如,[0,1,2,4,5,6,7] 可能会变为 [4,5,6,7,0,1,2]
给定一个目标值,去数组中查询这个值。如果找到,则返回索引,否则返回-1。
可以假设数组中没有重复值。
示例:
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
思路
如果没有旋转,就是有序数组,那么查找一个元素的位置有一个经典的方法——二分法。
本题对有序数组进行了旋转,因此二分法也需要做出一些调整,主要体现在选择左半区域还是右半区域作为下一次查询的子串。
对于经典的二分法,如果目标值小于中位数,则下一次查询选择左半区域,否则,选择右半区域。
对于本题,以图为例,数组首元素的索引为 l,尾元素的索引为 u,中位数的索引为 mid。由于旋转而得到的,因此可以看到有一个低谷,是最高值和最低值相邻的地方。
选择下一次搜索的区域时,还需要考虑中位数和首尾两个元素之间的大小关系:
- 如果 nums[mid] > nums[l],则说明低谷位于右半部分。
这时,如果 nums[l] < target < nums[mid],则需要选择左半区域,否则选择右半区域。 - 如果 nums[mid] < nums[l],则说明低谷位于左半部分。
这时,如果 nums[mid] < target < nums[u],则需要选择右半区域,否则选择左半区域。
算法复的时间复杂度与经典二分法相同,为 O(logn)。
python实现
def search(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
二分法。
"""
if not nums:
return -1
l, u = 0, len(nums)-1
while(l <= u):
# 长度为1或2
if u - l <= 1:
try:
return l + nums[l:u+1].index(target)
except:
return -1
mid = int((l + u) / 2)
if nums[mid] == target:
return mid
if nums[mid] > nums[l]:
# 说明mid落在了左半部分
if target > nums[mid]:
l = mid + 1
elif target >= nums[l]:
u = mid-1
else:
l = mid + 1
else:
if target < nums[mid]:
u = mid - 1
elif target <= nums[u]:
l = mid + 1
else:
u = mid - 1
if '__main__' == __name__:
nums = [4,5,6,7,0,1,2]
target = 0
print(search(nums, target))