#P4077. 搜索旋转排序数组
-
ID: 2318
Tried: 52
Accepted: 25
Difficulty: 5
搜索旋转排序数组
题目内容
整数数组 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)的算法解决此问题。
输入描述
- 第一行输入一个整数
n，表示数组的长度。 - 第二行输入
n个整数，表示旋转后的数组nums。 - 第三行输入一个整数
target，表示需要查找的目标值。
输出描述
- 输出一个整数，表示目标值
target在数组中的索引，若不存在则输出-1。
样例
样例 1
输入
7
4 5 6 7 0 1 2
0
输出
4
样例 2
输入
7
4 5 6 7 0 1 2
3
输出
-1
样例 3
输入
1
1
0
输出
-1
提示：
- 1<=nums.length<=5000
- −104<=nums[i]<=104
- nums中的每个值都独一无二
- 题目数据保证 nums 在预先未知的某个下标上进行了旋转
- −104<=target<=104
搜索旋转排序数组
题解思路
本题要求 O(logn) 的时间复杂度，因此我们必须使用 二分查找。
1. 旋转数组的特点
旋转数组由两个递增的子数组拼接而成，例如：
原数组: [0, 1, 2, 4, 5, 6, 7]
旋转后: [4, 5, 6, 7, 0, 1, 2] （旋转点在 7 之后）
由于数组仍保持局部有序，我们可以通过二分查找找到 target。
2. 二分查找思路
在 nums[left] 到 nums[mid] 和 nums[mid] 到 nums[right] 之间 至少有一部分是有序的：
- 如果
nums[left] <= nums[mid]，说明[left, mid]这部分是有序的。- 若
target在[left, mid]范围内，搜索左侧。 - 否则搜索右侧。
- 若
- 否则
[mid, right]是有序的：- 若
target在[mid, right]范围内，搜索右侧。 - 否则搜索左侧。
- 若
复杂度分析
- 时间复杂度：O(logn)，二分查找的每次操作都将搜索区间缩小一半。
- 空间复杂度：O(1)，仅使用常数级别的额外空间。
代码实现
Python 代码
import sys
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# 判断哪一部分是有序的
if nums[left] <= nums[mid]: # 左半部分有序
if nums[left] <= target < nums[mid]: # 目标值在左侧
right = mid - 1
else:
left = mid + 1
else: # 右半部分有序
if nums[mid] < target <= nums[right]: # 目标值在右侧
left = mid + 1
else:
right = mid - 1
return -1
# 读取输入
n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().split()))
target = int(sys.stdin.readline().strip())
# 输出结果
print(search(nums, target))
Java 代码
import java.util.Scanner;
public class Main {
public static int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
// 判断哪一部分是有序的
if (nums[left] <= nums[mid]) { // 左半部分有序
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // 右半部分有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
int target = scanner.nextInt();
System.out.println(search(nums, target));
}
}
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
// 判断哪一部分是有序的
if (nums[left] <= nums[mid]) { // 左半部分有序
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // 右半部分有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int target;
cin >> target;
cout << search(nums, target) << endl;
return 0;
}