leetcode81:搜索旋转排序数组II

原题地址：81. 搜索旋转排序数组 II - 力扣（LeetCode）

题目描述

已知存在一个按非降序排列的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

解题思路

• 问题概述：

  • 给定一个旋转排序数组 nums 和一个目标值 target，判断 target 是否存在于数组中。数组中的元素可能是有重复的。

• 问题分析：

  • 这个问题可以通过 二分查找 来优化时间复杂度。虽然数组是旋转过的，但是仍然有一定的规律性，可以利用二分查找的思想进行解题。
  • 关键点是数组有两个部分：一部分是递增的，另一部分是递增的旋转过后的部分。我们通过判断数组的中间元素与左右边界元素的关系来决定搜索的范围。

• 具体步骤：

  • 利用二分查找的思想，不断缩小查找范围。
  • 判断 nums[mid] 和 nums[low] 的关系：
    • 如果 nums[low] <= nums[mid]，说明左半部分是有序的。
      • 如果 target 在左半部分的范围内，更新右边界；否则，更新左边界。
    • 如果 nums[mid] <= nums[high]，说明右半部分是有序的。
      • 如果 target 在右半部分的范围内，更新左边界；否则，更新右边界。

  通过这种方式，我们在 O(log n) 的时间复杂度内找到目标值（如果存在的话）。

源码实现

class Solution {
    public boolean search(int[] nums, int target) {
        // 边界情况：如果数组为空，直接返回false
        if (nums == null || nums.length == 0) {
            return false;
        }

        int low = 0, high = nums.length - 1;

        // 使用二分查找
        while (low <= high) {
            int mid = low + (high - low) / 2;

            // 如果找到了目标值，直接返回true
            if (nums[mid] == target) {
                return true;
            }

            // 如果左边部分是有序的
            if (nums[low] <= nums[mid]) {
                // 如果target在左边部分的范围内
                if (nums[low] <= target && target < nums[mid]) {
                    high = mid - 1; // 更新右边界
                } else {
                    low = mid + 1; // 更新左边界
                }
            }
            // 如果右边部分是有序的
            else {
                // 如果target在右边部分的范围内
                if (nums[mid] < target && target <= nums[high]) {
                    low = mid + 1; // 更新左边界
                } else {
                    high = mid - 1; // 更新右边界
                }
            }
        }

        // 如果找不到目标值，返回false
        return false;
    }
}

复杂度分析

1. 时间复杂度：

   • 二分查找的时间复杂度是 O(log n)，其中 n 是数组的长度。即使数组是旋转排序的，我们也可以通过调整查找区间来维持二分查找的效率。

2. 空间复杂度：

   • 该算法只使用了常数空间来存储变量（如 low, high, mid），所以空间复杂度为 O(1)