力扣第33题:搜索旋转排序数组

时间:2024-11-05 07:17:29

力扣第33题:搜索旋转排序数组

题目描述

在一个旋转排序数组中搜索一个目标值,并返回其索引。若未找到目标值,则返回 -1。旋转排序数组是指一个升序排列的数组在某个未知的旋转点被旋转。例如,nums = [4, 5, 6, 7, 0, 1, 2]。你可以假设数组中不存在重复元素。

示例

输入: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
输出: 4

解题思路

我们可以利用二分查找的思路,因为在旋转排序数组中,一半的部分总是有序的。通过比较中间值和左右边界值的大小关系,可以判断哪一部分是有序的,再根据目标值的位置来缩小搜索区间。

具体步骤

  1. 定义左右指针:用 leftright 指针指向数组的左右边界。
  2. 中间值的计算:计算 mid 作为 leftright 的中间索引。
  3. 比较中间值
    • 如果 nums[mid] == target,直接返回 mid
    • 如果 nums[left] <= nums[mid](即左半部分是有序的):
      • 判断目标值是否在左半部分,如果在,更新 right = mid - 1,否则更新 left = mid + 1
    • 如果右半部分是有序的(即 nums[mid] < nums[right]):
      • 判断目标值是否在右半部分,如果在,更新 left = mid + 1,否则更新 right = mid - 1
  4. 返回结果:循环结束后如果没有找到目标值,返回 -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;
  • leftright 指针用于表示当前搜索范围的左右边界。
    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],说明从 leftmid 的部分是连续递增的。
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
  • 在左半部分有序的情况下,判断目标值 target 是否在 leftmid 的范围内:
    • 如果是,移动 right 指针以缩小范围至左半部分;
    • 否则,移动 left 指针至右半部分继续搜索。
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
  • 如果左半部分无序,那么右半部分必定有序。使用类似方法判断目标值在右半部分的位置,更新 leftright 指针。
    }
    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