62 · 搜索旋转排序数组
描述
给定一个有序数组,但是数组以某个元素作为支点进行了旋转(比如,0 1 2 4 5 6 7
可能成为4 5 6 7 0 1 2
)。给定一个目标值target
进行搜索,如果在数组中找到目标值返回数组中的索引位置,否则返回-1
。你可以假设数组中不存在重复的元素。
背完这套刷题模板,真的不一样!
样例
样例 1:
输入:
数组 = [4, 5, 1, 2, 3]
target = 1
输出:
2
解释:
1在数组中对应索引位置为2。
样例 2:
输入:
数组 = [4, 5, 1, 2, 3]
target = 0
输出:
-1
解释:
0不在数组中,返回-1。
挑战
O(logN) 时间限制
from typing import (
List,
)
class Solution:
"""
@param a: an integer rotated sorted array
@param target: an integer to be searched
@return: an integer
"""
def search(self, a: List[int], target: int) -> int:
# write your code here
def find_peak():
l, r = 0, len(a) - 1
while l < r - 1:
mid = (l + r) >> 1
if a[mid] > a[0]:
l = mid
else:
r = mid
if a[l] < a[r]:
return r
return l
def bin_search(l, r):
while l < r - 1:
mid = (l + r) >> 1
if a[mid] < target:
l = mid
else:
r = mid
if a[l] == target:
return l
if a[r] == target:
return r
return -1
if not a:
return -1
if a[0] <= a[-1]:
return bin_search(0, len(a)-1)
peak = find_peak()
#在前半段搜索
if a[0] <= target <= a[peak]:
return bin_search(0, peak)
#在后半段搜索
return bin_search(peak+1, len(a)-1)
逻辑非常简单清晰!!!不要再去用以前那种复杂的解法了。。。几个关系给你整蒙逼!!!
比如下面这种,就是用到夹逼的思想:
从两边不断靠近target的值。
class Solution:
"""
@param A: an integer rotated sorted array
@param target: an integer to be searched
@return: an integer
"""
def search(self, A, target):
if not A:
return -1
start, end = 0, len(A) - 1
while start + 1 < end:
mid = (start + end) // 2
if A[mid] >= A[start]:
if A[start] <= target <= A[mid]:
end = mid
else:
start = mid
else:
if A[mid] <= target <= A[end]:
start = mid
else:
end = mid
if A[start] == target:
return start
if A[end] == target:
return end
return -1
if A[mid] >= A[start]:
if A[start] <= target <= A[mid]: ==》表示在左半边升序部分
else: if A[mid] <= target <= A[end]:==》表示在右半边升序部分
要求逻辑分析非常严谨。。。
标签:二分,return,target,mid,start,搜索,数组,integer From: https://blog.51cto.com/u_11908275/6384678