描述
Suppose an array sorted in ascending order 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.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
1
2
| Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
|
Example 2:
1
2
| Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
|
分析
求循环有序数组某个元素的下标，仍然还是用二分法，关键是要清楚怎么判断 target 是在序列的左边还是右边，首先我们可以知道的，当把循环有序数组切成两部分时，一定是一部分序列有序，另一部分序列无需或有序，而 nums[mid] < nums[right] 时，右边一定是有序的，如果 nums[mid] 在右边的序列中，那么就继续遍历右边，否则遍历左边，对于左边有序的情况也是一样。
解决方案1(Python)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) / 2
if nums[mid] == target:
return mid
if nums[mid] < nums[right]:
if nums[mid] < target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
else:
if nums[left] <= target and target < nums[mid]:
right = mid -1
else:
left = mid + 1
return -1
|
解决方案2（Golang）
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
| func search(nums []int, target int) int {
if len(nums) == 0 {
return -1
}
left := 0
right := len(nums) - 1
for left <= right {
mid := (left+right) / 2
if nums[mid] == target {
return mid
}
if nums[mid] < nums[right] {
if nums[mid] <= target && nums[right] >= target {
left = mid + 1
} else {
right = mid - 1
}
} else {
if nums[mid] >= target && nums[left] <= target {
right = mid - 1
} else {
left = mid + 1
}
}
}
return -1
}
|
相关问题