Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Solution
- 二分查找
- 对于m来说，要么左面递增，要么右面递增，然后分别考虑target 在[l,m] 和 [m,r]中的情况
(Search-in-Rotated-Sorted-Array.py) download
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
| class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
l = 0
r = len(nums)-1
if len(nums) == 0:
return -1
while l <= r:
m = (l+r)/2
if nums[m] == target:
return m
# m左面递增
if nums[l] <= nums[m]:
if nums[l] <= target < nums[m]:
r = m-1
else:
l = m+1
# m右边递增
else:
if nums[m] < target <= nums[r]:
l = m+1
else:
r = m-1
return -1
|