33.搜索旋转排序数组 Search in Rotated Sorted Array
题解二分法算法流程：复杂度分析PythonJava(待完成)
题解
本题看到时间复杂度需要在
O
(
log
n
)
O(\log n)
O(logn)级别，所以想到二分查找 本题两个特殊之处
有序，可使用二分查找旋转数组，需要找到旋转点，才能进行二分查找
二分法
算法流程：
特判：数组长度为0，返回-1. 数组长度为1，若
n
u
m
s
[
0
]
=
=
t
a
r
g
e
t
nums[0]==target
nums[0]==target,返回0，否则返回-1。（这个特例无法按照算法流程计算，所以需要单独判断）二分法寻找旋转点：
如果首元素小于尾元素，说明未旋转，返回0定义左指针
l
l
l和右指针
r
r
r，当
l
<
=
r
l<=r
l<=r时，进入循环，接下来有两种写法，但是始终返回旋转点为最小值的索引：
r
o
t
a
t
e
=
(
l
+
r
)
/
/
2
rotate=(l+r)//2
rotate=(l+r)//2，如果
n
u
m
s
[
r
o
t
a
t
e
]
<
n
u
m
s
[
r
o
t
a
t
e
−
1
]
nums[rotate]<nums[rotate-1]
nums[rotate]<nums[rotate−1],此时返回
r
o
t
a
t
e
rotate
rotate，判断是否满足
n
u
m
s
[
r
o
t
a
t
e
]
>
n
u
m
s
[
r
]
nums[rotate]>nums[r]
nums[rotate]>nums[r]，若满足说明旋转点在右端，令
l
=
r
o
t
a
t
e
+
1
l=rotate+1
l=rotate+1,否则在左端，令
r
=
r
o
t
a
t
e
−
1
r=rotate-1
r=rotate−1。
r
o
t
a
t
e
=
(
l
+
r
)
/
/
2
rotate=(l+r)//2
rotate=(l+r)//2，如果
n
u
m
s
[
r
o
t
a
t
e
]
>
n
u
m
s
[
r
o
t
a
t
e
+
1
]
nums[rotate]>nums[rotate+1]
nums[rotate]>nums[rotate+1],此时返回
r
o
t
a
t
e
+
1
rotate+1
rotate+1，判断是否满足
n
u
m
s
[
r
o
t
a
t
e
]
<
n
u
m
s
[
l
]
nums[rotate]<nums[l]
nums[rotate]<nums[l]，若满足说明旋转点在左端，令
r
=
r
o
t
a
t
e
−
1
r=rotate-1
r=rotate−1,否则在右端，令
l
=
r
o
t
a
t
e
+
1
l=rotate+1
l=rotate+1。 若旋转点索引
r
o
t
a
t
e
i
n
d
e
x
=
0
rotateindex=0
rotateindex=0，说明未旋转，则直接二分查找
f
i
n
d
(
0
,
n
−
1
)
find(0,n-1)
find(0,n−1)，返回索引判断
t
a
r
g
e
t
>
=
n
u
m
s
[
0
]
target>=nums[0]
target>=nums[0]，如果满足，说明在旋转段的较大段，
f
i
n
d
(
0
,
r
o
t
a
t
e
i
n
d
e
x
)
find(0,rotateindex)
find(0,rotateindex)，否则
f
i
n
d
(
r
o
t
a
t
e
i
n
d
e
x
,
n
−
1
)
find(rotateindex,n-1)
find(rotateindex,n−1)
复杂度分析
时间复杂度：
O
(
log
n
)
O(\log n)
O(logn)+
O
(
log
n
)
O(\log n)
O(logn),
O
(
log
n
)
O(\log n)
O(logn)空间复杂度：
O
(
1
)
O(1)
O(1)
Python
class Solution:
def search(self
, nums
: List
[int], target
: int) -> int:
def find_rotateindex(l
,r
):
if(nums
[l
]<nums
[r
]):
return 0
while(l
<=r
):
rotate
=(l
+r
)//2
if(nums
[rotate
]<nums
[rotate
-1]):
return rotate
if(nums
[rotate
]>nums
[r
]):
l
=rotate
+1
else:
r
=rotate
-1
def find(l
,r
):
while(l
<=r
):
mid
=(l
+r
)//2
if(nums
[mid
]==target
):
return mid
if(nums
[mid
]>target
):
r
=mid
-1
else:
l
=mid
+1
return -1
n
=len(nums
)
if(n
==0):
return -1
if(n
==1):
return 0 if(nums
[0]==target
) else -1
rotateindex
=find_rotateindex
(0,n
-1)
if(rotateindex
==0):
return find
(0,n
-1)
if(target
>=nums
[0]):
return find
(0,rotateindex
)
else:
return find
(rotateindex
,n
-1)
Java(待完成)
