-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathleetcode_33.py
More file actions
37 lines (31 loc) · 861 Bytes
/
leetcode_33.py
File metadata and controls
37 lines (31 loc) · 861 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# coding=utf-8
from typing import List
class Solution:
"""
搜索旋转排序数组
"""
def search(self, nums: List[int], target: int) -> int:
"""
Time: O(log(n)), Space: O(1)
:param nums:
:param target:
:return:
"""
if not nums:
return -1
low, high = 0, len(nums) - 1
while low <= high:
mid = low + (high - low) // 2
if nums[mid] == target:
return mid
if nums[mid] >= nums[low]:
if nums[low] <= target < nums[mid]:
high = mid - 1
else:
low = mid + 1
else:
if nums[mid] < target <= nums[high]:
low = mid + 1
else:
high = mid - 1
return -1