题目描述
搜索旋转数组。给定一个排序后的数组,包含n个整数,但这个数组已被旋转过很多次了,次数不详。请编写代码找出数组中的某个元素,假设数组元素原先是按升序排列的。若有多个相同元素,返回索引值最小的一个。
示例1:
输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8(元素5在该数组中的索引)
示例2:
输入:arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出:-1 (没有找到)
提示:
- arr 长度范围在[1, 1000000]之间
解法
方法一:二分查找
我们定义二分查找的左边界 $l=0$,右边界 $r=n-1$,其中 $n$ 为数组的长度。
每次在二分查找的过程中,我们会得到当前的中点 $mid=(l+r)/2$。
- 如果 $nums[mid] \gt nums[r]$,说明 $[l,mid]$ 是有序的,此时如果 $nums[l] \le target \le nums[mid]$,说明 $target$ 位于 $[l,mid]$,否则 $target$ 位于 $[mid+1,r]$。
- 如果 $nums[mid] \lt nums[r]$,说明 $[mid+1,r]$ 是有序的,此时如果 $nums[mid] \lt target \le nums[r]$,说明 $target$ 位于 $[mid+1,r]$,否则 $target$ 位于 $[l,mid]$。
- 如果 $nums[mid] = nums[r]$,说明元素 $nums[mid]$ 和 $nums[r]$ 相等,此时无法判断 $target$ 位于哪个区间,我们只能将 $r$ 减少 $1$。
二分查找结束后,如果 $nums[l] = target$,则说明数组中存在目标值 $target$,否则说明不存在。
注意,如果一开始 $nums[l] = nums[r]$,我们循环将 $r$ 减少 $1$,直到 $nums[l] \ne nums[r]$。
时间复杂度近似 $O(\log n)$,空间复杂度 $O(1)$。其中 $n$ 为数组的长度。
相似题目:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution:
def search(self, arr: List[int], target: int) -> int:
l, r = 0, len(arr) - 1
while arr[l] == arr[r]:
r -= 1
while l < r:
mid = (l + r) >> 1
if arr[mid] > arr[r]:
if arr[l] <= target <= arr[mid]:
r = mid
else:
l = mid + 1
elif arr[mid] < arr[r]:
if arr[mid] < target <= arr[r]:
l = mid + 1
else:
r = mid
else:
r -= 1
return l if arr[l] == 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
24
25
26
27 | class Solution {
public int search(int[] arr, int target) {
int l = 0, r = arr.length - 1;
while (arr[l] == arr[r]) {
--r;
}
while (l < r) {
int mid = (l + r) >> 1;
if (arr[mid] > arr[r]) {
if (arr[l] <= target && target <= arr[mid]) {
r = mid;
} else {
l = mid + 1;
}
} else if (arr[mid] < arr[r]) {
if (arr[mid] < target && target <= arr[r]) {
l = mid + 1;
} else {
r = mid;
}
} else {
--r;
}
}
return arr[l] == target ? l : -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
28 | class Solution {
public:
int search(vector<int>& arr, int target) {
int l = 0, r = arr.size() - 1;
while (arr[l] == arr[r]) {
--r;
}
while (l < r) {
int mid = (l + r) >> 1;
if (arr[mid] > arr[r]) {
if (arr[l] <= target && target <= arr[mid]) {
r = mid;
} else {
l = mid + 1;
}
} else if (arr[mid] < arr[r]) {
if (arr[mid] < target && target <= arr[r]) {
l = mid + 1;
} else {
r = mid;
}
} else {
--r;
}
}
return arr[l] == target ? l : -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
28 | func search(arr []int, target int) int {
l, r := 0, len(arr)-1
for arr[l] == arr[r] {
r--
}
for l < r {
mid := (l + r) >> 1
if arr[mid] > arr[r] {
if arr[l] <= target && target <= arr[mid] {
r = mid
} else {
l = mid + 1
}
} else if arr[mid] < arr[r] {
if arr[mid] < target && target <= arr[r] {
l = mid + 1
} else {
r = mid
}
} else {
r--
}
}
if arr[l] == target {
return l
}
return -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 | function search(arr: number[], target: number): number {
let [l, r] = [0, arr.length - 1];
while (arr[l] === arr[r]) {
--r;
}
while (l < r) {
const mid = (l + r) >> 1;
if (arr[mid] > arr[r]) {
if (arr[l] <= target && target <= arr[mid]) {
r = mid;
} else {
l = mid + 1;
}
} else if (arr[mid] < arr[r]) {
if (arr[mid] < target && target <= arr[r]) {
l = mid + 1;
} else {
r = mid;
}
} else {
--r;
}
}
return arr[l] === target ? l : -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
28
29
30
31 | class Solution {
func search(_ arr: [Int], _ target: Int) -> Int {
var l = 0
var r = arr.count - 1
while arr[l] == arr[r] && l < r {
r -= 1
}
while l < r {
let mid = (l + r) >> 1
if arr[mid] > arr[r] {
if arr[l] <= target && target <= arr[mid] {
r = mid
} else {
l = mid + 1
}
} else if arr[mid] < arr[r] {
if arr[mid] < target && target <= arr[r] {
l = mid + 1
} else {
r = mid
}
} else {
r -= 1
}
}
return arr[l] == target ? l : -1
}
}
|