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

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

题目描述

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

示例：

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

解题思路

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

具体步骤

1. 定义左右指针：用 left 和 right 指针指向数组的左右边界。
2. 中间值的计算：计算 mid 作为 left 和 right 的中间索引。
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;

• 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