力扣第三十三题——搜索旋转排序数组

内容介绍

整数数组 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) 的算法解决此问题。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

完整代码

 class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

思路详解

方法概述

search方法实现了一个改进的二分查找算法，适用于经过旋转的有序数组。旋转数组的特点是，数组的一部分是有序的，另一部分也是有序的，但是两部分之间的顺序被打乱了。

思路详解

1. 边界情况处理：

   • 如果数组长度为0，直接返回-1，因为没有元素可以查找。
   • 如果数组长度为1，检查该元素是否为目标值，如果是则返回索引0，否则返回-1。

2. 初始化二分查找的左右指针：

   • l（左指针）初始化为0。
   • r（右指针）初始化为数组长度减1。

3. 二分查找循环：

   • 当l小于等于r时，进行以下操作：
     • 计算中间位置mid。
     • 如果nums[mid]等于目标值target，直接返回mid。

4. 判断中间位置的元素与数组首元素的关系：

   • 如果nums[0]小于等于nums[mid]，说明左半部分是有序的：
     • 如果目标值target在nums[0]和nums[mid]之间，则将右指针r移动到mid - 1。
     • 否则，将左指针l移动到mid + 1。
   • 如果nums[0]大于nums[mid]，说明右半部分是有序的：
     • 如果目标值target在nums[mid]和nums[n - 1]之间，则将左指针l移动到mid + 1。
     • 否则，将右指针r移动到mid - 1。

5. 循环结束：

   • 如果循环结束还没有找到目标值，说明目标值不在数组中，返回-1。

代码注释

以下是代码中关键步骤的注释：

public int search(int[] nums, int target) {
    int n = nums.length;
    if (n == 0) {
        return -1; // 数组为空，直接返回-1
    }
    if (n == 1) {
        return nums[0] == target ? 0 : -1; // 数组只有一个元素，检查是否为目标值
    }
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2; // 计算中间位置
        if (nums[mid] == target) {
            return mid; // 找到目标值，返回索引
        }
        if (nums[0] <= nums[mid]) {
            // 左半部分有序
            if (nums[0] <= target && target < nums[mid]) {
                r = mid - 1; // 目标值在左半部分
            } else {
                l = mid + 1; // 目标值在右半部分
            }
        } else {
            // 右半部分有序
            if (nums[mid] < target && target <= nums[n - 1]) {
                l = mid + 1; // 目标值在右半部分
            } else {
                r = mid - 1; // 目标值在左半部分
            }
        }
    }
    return -1; // 未找到目标值，返回-1
}

知识点精炼

二分查找算法（Binary Search）

• 基本概念：一种在有序数组中查找特定元素的搜索算法，通过不断将搜索区间减半来提高搜索效率。
• 时间复杂度：O(log n)，其中n是数组的长度。

2. 循环数组的处理

• 旋转数组：一个有序数组在某些点上被旋转，使得数组的一部分有序，另一部分同样有序，但整体不再有序。
• 二分查找的适应：通过比较中间元素与数组首元素，确定哪部分是有序的，从而决定搜索方向。

3. 边界条件处理

• 空数组：如果数组为空，直接返回-1，因为没有元素可以查找。
• 单元素数组：如果数组只有一个元素，直接比较该元素与目标值。

4. 循环与递归的选择

• 循环实现：使用while循环进行二分查找，避免了递归可能带来的额外开销。

5. 中间位置的取值

• 防止溢出：使用(l + r) / 2计算中间位置，而非(l + r) >> 1，虽然后者在位运算上更高效，但在此场景下避免了整型溢出的风险。

6. 搜索区间的调整

• 左半部分有序：如果中间元素大于等于首元素，说明左半部分是有序的，根据目标值的位置调整搜索区间。
• 右半部分有序：如果中间元素小于首元素，说明右半部分是有序的，同样根据目标值的位置调整搜索区间。

7. 返回结果

• 找到目标值：如果中间元素等于目标值，返回中间位置的索引。
• 未找到目标值：如果循环结束仍未找到目标值，返回-1。

8. 算法优化

• 避免重复比较：在每次循环中，仅比较一次中间元素与目标值，减少了不必要的比较次数。

通过以上知识点，我们可以看到，虽然代码实现的是二分查找，但针对旋转数组的特性进行了适当的调整，使得算法能够适应这种特殊的有序数组。这些知识点对于理解和实现高效的搜索算法至关重要。