题目描述
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104nums 中的每个值都 独一无二- 题目数据保证
nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104
解法
方法一：二分查找
我们使用二分，将数组分割成 $[left,.. mid]$, $[mid + 1,.. right]$ 两部分，这时候可以发现，其中有一部分一定是有序的。
因此，我们可以根据有序的那一部分，判断 $target$ 是否在这一部分中：
- 若 $[0,.. mid]$ 范围内的元素构成有序数组：
- 若满足 $nums[0] \leq target \leq nums[mid]$，那么我们搜索范围可以缩小为 $[left,.. mid]$；
- 否则，在 $[mid + 1,.. right]$ 中查找；
- 若 $[mid + 1, n - 1]$ 范围内的元素构成有序数组：
- 若满足 $nums[mid] \lt target \leq nums[n - 1]$，那么我们搜索范围可以缩小为 $[mid + 1,.. right]$；
- 否则，在 $[left,.. mid]$ 中查找。
二分查找终止条件是 $left \geq right$，若结束后发现 $nums[left]$ 与 $target$ 不等，说明数组中不存在值为 $target$ 的元素，返回 $-1$，否则返回下标 $left$。
时间复杂度 $O(\log n)$，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n - 1
while left < right:
mid = (left + right) >> 1
if nums[0] <= nums[mid]:
if nums[0] <= target <= nums[mid]:
right = mid
else:
left = mid + 1
else:
if nums[mid] < target <= nums[n - 1]:
left = mid + 1
else:
right = mid
return left if nums[left] == target else -1
|
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 {
public int search(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1;
while (left < right) {
int mid = (left + right) >> 1;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target <= nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
left = mid + 1;
} else {
right = mid;
}
}
}
return nums[left] == target ? left : -1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left < right) {
int mid = (left + right) >> 1;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target <= nums[mid])
right = mid;
else
left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[n - 1])
left = mid + 1;
else
right = mid;
}
}
return nums[left] == target ? left : -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | func search(nums []int, target int) int {
n := len(nums)
left, right := 0, n-1
for left < right {
mid := (left + right) >> 1
if nums[0] <= nums[mid] {
if nums[0] <= target && target <= nums[mid] {
right = mid
} else {
left = mid + 1
}
} else {
if nums[mid] < target && target <= nums[n-1] {
left = mid + 1
} else {
right = mid
}
}
}
if nums[left] == target {
return left
}
return -1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | function search(nums: number[], target: number): number {
const n = nums.length;
let left = 0,
right = n - 1;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target <= nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
left = mid + 1;
} else {
right = mid;
}
}
}
return nums[left] == target ? left : -1;
}
|
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 | impl Solution {
pub fn search(nums: Vec<i32>, target: i32) -> i32 {
let mut l = 0;
let mut r = nums.len() - 1;
while l <= r {
let mid = (l + r) >> 1;
if nums[mid] == target {
return mid as i32;
}
if nums[l] <= nums[mid] {
if target < nums[mid] && target >= nums[l] {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if target > nums[mid] && target <= nums[r] {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
-1
}
}
|
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 | /**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
const n = nums.length;
let left = 0,
right = n - 1;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target <= nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
left = mid + 1;
} else {
right = mid;
}
}
}
return nums[left] == target ? left : -1;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
/**
* @param integer[] $nums
* @param integer $target
* @return integer
*/
function search($nums, $target) {
$foundKey = -1;
foreach ($nums as $key => $value) {
if ($value === $target) {
$foundKey = $key;
}
}
return $foundKey;
}
}
|