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,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

二、解题思路

1. 初始化两个指针，left 和 right，分别指向数组的开始和结束。
2. 当 left 小于 right 时，执行以下步骤： a. 计算中间位置 mid。 b. 如果 nums[mid] 等于 target，则返回 mid。 c. 判断 nums[left] 和 nums[mid] 之间的值是否有序：
   • 如果有序，说明 target 必须在 left 和 mid 之间，更新 right 为 mid - 1。
   • 如果无序，说明 target 必须在 mid 和 right 之间，更新 left 为 mid + 1。
3. 如果循环结束还没有找到 target，则返回 -1。

三、具体代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // 如果找到了目标值
            if (nums[mid] == target) {
                return mid;
            }
            
            // 判断左右两边哪一边是有序的
            if (nums[left] <= nums[mid]) {
                // 左边有序，target 在左边
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // 右边有序，target 在右边
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        
        // 循环结束，如果 left 等于 right 且 nums[left] 等于 target，则返回 left
        // 否则返回 -1
        return nums[left] == target ? left : -1;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 时间复杂度是 O(log n)。
• 这是因为在每次迭代中，搜索范围都会减半。
• 这是二分查找算法的典型特征，其中 n 是数组的长度。
• 在最坏的情况下，需要进行 log(n) 次迭代才能找到目标值或确定目标值不存在。

2. 空间复杂度

• 空间复杂度是 O(1)。
• 这个算法是原地进行的，不需要额外的存储空间。
• 所有的计算都是在常量级别的额外空间内完成的，例如使用几个辅助变量（left, right, mid）。
• 这些变量的数量不随着输入数据的规模变化，因此空间复杂度是常数级别的。

五、总结知识点

1. 二分查找算法（Binary Search）：

• 这是一种在有序数组中查找特定元素的高效算法。
• 通过不断将搜索范围减半，二分查找可以在对数时间内找到目标值或确定目标值不存在。

2. 旋转排序数组的处理：

• 由于数组是旋转过的，它不再是完全有序的，这就需要在二分查找的基础上进行调整。
• 通过比较数组的两端（left 和 right）以及中间点（mid）的值，可以确定哪一半是有序的，并据此调整搜索范围。

3. 条件判断和循环控制：

• 使用 while 循环来重复执行二分查找的过程，直到找到目标值或搜索范围为空。
• 使用 if 和 else 语句来判断数组的哪一半是有序的，并据此更新搜索范围的边界。

4. 数组索引的更新：

• 根据中间点 mid 的值与目标值 target 的关系，以及数组的有序性，更新 left 和 right 的值。

5. 返回值的处理：

• 如果在循环结束后 left 和 right 相遇，并且 nums[left] 等于 target，则返回 left。
• 如果 left 和 right 相遇，但 nums[left] 不等于 target，则返回 -1 表示目标值不存在于数组中。

6. 防止整数溢出：

• 在计算 mid 时，使用 left + (right - left) / 2 而不是 (left + right) / 2 来避免可能的整数溢出问题。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。