力扣第33题:搜索旋转排序数组
题目描述
在一个旋转排序数组中搜索一个目标值,并返回其索引。若未找到目标值,则返回 -1。旋转排序数组是指一个升序排列的数组在某个未知的旋转点被旋转。例如,nums = [4, 5, 6, 7, 0, 1, 2]
。你可以假设数组中不存在重复元素。
示例:
输入: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
输出: 4
解题思路
我们可以利用二分查找的思路,因为在旋转排序数组中,一半的部分总是有序的。通过比较中间值和左右边界值的大小关系,可以判断哪一部分是有序的,再根据目标值的位置来缩小搜索区间。
具体步骤
-
定义左右指针:用
left
和right
指针指向数组的左右边界。 -
中间值的计算:计算
mid
作为left
和right
的中间索引。 -
比较中间值:
- 如果
nums[mid] == target
,直接返回mid
。 - 如果
nums[left] <= nums[mid]
(即左半部分是有序的):- 判断目标值是否在左半部分,如果在,更新
right = mid - 1
,否则更新left = mid + 1
。
- 判断目标值是否在左半部分,如果在,更新
- 如果右半部分是有序的(即
nums[mid] < nums[right]
):- 判断目标值是否在右半部分,如果在,更新
left = mid + 1
,否则更新right = mid - 1
。
- 判断目标值是否在右半部分,如果在,更新
- 如果
- 返回结果:循环结束后如果没有找到目标值,返回 -1。
代码实现
以下是完整的代码实现:
#include <stdio.h>
int search(int* nums, int numsSize, int target) {
int left = 0, right = numsSize - 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 search(int* nums, int numsSize, int target) {
int left = 0, right = numsSize - 1;
-
left
和right
指针用于表示当前搜索范围的左右边界。
while (left <= right) {
int mid = left + (right - left) / 2;
- 在
while
循环中,当left
小于或等于right
时,计算中间索引mid
。
if (nums[mid] == target) {
return mid; // 找到目标值,直接返回索引
}
- 检查
nums[mid]
是否等于目标值target
,如果相等,则返回mid
。
// 判断左半部分是否有序
if (nums[left] <= nums[mid]) {
- 判断左半部分是否有序。若
nums[left] <= nums[mid]
,说明从left
到mid
的部分是连续递增的。
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
- 在左半部分有序的情况下,判断目标值
target
是否在left
到mid
的范围内:- 如果是,移动
right
指针以缩小范围至左半部分; - 否则,移动
left
指针至右半部分继续搜索。
- 如果是,移动
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
- 如果左半部分无序,那么右半部分必定有序。使用类似方法判断目标值在右半部分的位置,更新
left
或right
指针。
}
return -1;
}
- 当
while
循环结束仍未找到目标值,则返回-1
表示不存在目标值。
时间复杂度
由于每次迭代后搜索区间缩小一半,时间复杂度为 O(log n)
,这是二分查找算法的标准复杂度。
总结
此算法利用旋转数组的一部分总是有序的性质,通过二分查找和分段判断有效缩小搜索范围,最终实现高效搜索。
示例
int main() {
int nums[] = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
int index = search(nums, 7, target);
printf("Target %d found at index: %d\n", target, index);
return 0;
}
输出结果:
Target 0 found at index: 4