搜索旋转排序数组

难度:

标签:

题目描述

整数数组 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
-10⁴ <= nums[i] <= 10⁴
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10⁴ <= target <= 10⁴

代码结果

运行时间: 44 ms, 内存: 15.1 MB

// Problem statement: Similar to the above, but this time using Java Streams.
 
// Approach: Streams are not directly used for searching due to their sequential nature and lack of index access. However, for the sake of demonstration, we can still use Streams to find the target by converting the array to a list and leveraging the indexOf method. This solution is not optimal in terms of performance (not O(log n)) but shows the use of Streams.
 
import java.util.*;
import java.util.stream.*;
 
public class SolutionWithStream {
    public int search(int[] nums, int target) {
        // Convert the array to a list and search for the target
        List<Integer> numList = Arrays.stream(nums).boxed().collect(Collectors.toList());
        return numList.indexOf(target); // Returns index if found, -1 if not
    }
}

解释

方法:

这个题解的思路是先通过二分查找找到旋转点，将数组分为两个有序的子数组。然后根据目标值和第一个元素的大小关系，确定在哪个子数组中进行二分查找。最后在选定的子数组中进行标准的二分查找，找到目标值的下标或确定目标值不存在。

时间复杂度:

O(log n)

空间复杂度:

O(1)

代码细节讲解

🦆

如何通过初始的二分查找准确找到数组的旋转点？

▷

在旋转排序数组中找到旋转点的关键是确定哪一部分是有序的。初始时，我们比较中间元素与数组的第一个元素。如果中间元素大于等于第一个元素，说明从第一个元素到中间元素之间的子数组是有序的，旋转点应该在中间元素的右侧或就是中间本身。反之，如果中间元素小于第一个元素，旋转点应在左侧。通过不断缩小查找范围，最终左指针 l 将指向旋转点。

🦆

在确定目标值属于哪个子数组进行查找时，是否有可能将目标值排除在外，特别是在极端的旋转情况下（如仅旋转一位）？

▷

目标值的定位是基于旋转点和目标值与第一个元素的比较来决定的。如果目标值大于等于第一个元素，搜索范围是从数组开始到旋转点；如果目标值小于第一个元素，搜索范围是从旋转点的下一个位置到数组末尾。即使在极端的旋转情况（如旋转一位或旋转 n-1 位），这种方法仍然有效，因为旋转点的定位将正确划分两个有序的子数组。

🦆

为什么选择在找到旋转点后，再使用二分查找在相应的子数组中搜索目标值，而不是直接在整个数组上应用某种变体的二分查找？

▷

虽然可以直接在整个旋转数组上使用一种变体的二分查找来寻找目标值，但这通常需要更复杂的条件判断来处理旋转的特性，增加了实现的复杂度和出错的可能性。通过首先找到旋转点，然后在确定的有序子数组上应用标准的二分查找，可以简化问题并利用二分查找的高效性。这种方法更直观，也更容易维护和理解。

🦆

在实现中，`mid = l + (r - l + 1) // 2` 使用了 `(r - l + 1)` 而不是 `(r - l)` 来计算 `mid`，这种计算方式对结果有何影响？

▷

使用 `(r - l + 1)` 的目的是在计算中值时向上取整，这样可以保证在 l 和 r 非常接近时，mid 能够向右偏移，从而避免在一些情况下陷入死循环。比如当 l 和 r 相等时，如果使用 `(r - l)` 计算，mid 将等于 l，可能导致无法进一步缩小查找范围。使用向上取整的方式，可以确保在所有情况下 l 和 r 都能有效地向旋转点靠拢，最终准确定位。

相关问题