C++ 中查找旋转排序数组的枢轴

引言

旋转排序数组在计算机科学和算法中非常有趣。旋转排序数组是指一个曾经有序的数组，但已围绕某个未知枢轴点进行了旋转。旋转可以是顺时针或逆时针的。旋转排序数组的主要问题是找到枢轴点，即发生旋转的索引。枢轴点信息对于数组的高效搜索、排序或其他操作至关重要。

问题陈述

给定一个旋转排序数组，我们希望找出枢轴点存在于何处，或者发生了旋转的索引是什么。这个枢轴点将数组分成两个子数组，每个子数组本身都是有序的。通过开发一种能够有效确定枢轴点的算法来解决此任务。

举个例子有助于阐明这个问题。假设您有一系列数字按以下方式排列：

4,5,6,7,0,1,2

在这种情况下，它的原始顺序遵循（另一个）序列：

0, 1, 2, 4, 5, 6 和 7。然而，它在索引 3（值为 7）处被扭转，形成了现在的状态；因此，它被称为“旋转”的旋转排序数组。因此，枢轴点位于索引 3。

为了解决这个挑战，我们可以采用各种算法和技术。其中一种就是二分查找，它速度快且具有对数时间复杂度，可以找到枢轴点。

过程：使用二分查找法寻找枢轴点

二分查找算法适用于需要快速查找有序数组中某个项的问题。旋转排序数组的情况可以通过定制二分查找来最小化我们的选择，直到我们找到枢轴点。

以下是使用二分查找方法查找枢轴点的一些步骤：

• 首先，我们将初始化两个指针，left 和 right，分别指向数组的第一个和最后一个元素。
• 只要 left 小于 right，就应该计算中间值。
• 如果 mid 处的元素与其右侧的元素进行比较。
• 如果 nums[mid] > nums[right]，则意味着枢轴必须位于 mid 的右侧，因此需要将 left=mid+1。
• 或者，如果它不大于（即小于或等于），则应通过令 right = mid 来更新。
• 出于这些原因，重复步骤 2-3，直到 left 和 right 收敛，这告诉我们已经找到了枢轴元素。

示例

让我们通过一个 C++ 代码片段来说明这种方法：

输出

Pivot element index: 4
Pivot element value: 0

说明

1. 初始化指针

• 首先，我们初始化两个指针 left 和 right，它们分别指向数组的第一个和最后一个元素。这最初将搜索空间定义为整个数组。

2. 计算中点

• 在二分查找的主循环中，我们使用公式 mid = left + (right - left) / 2 计算中间索引 mid。此公式确保 mid 始终更新为当前搜索空间的中点。

3. 将中间元素与右侧元素进行比较

• 在每次迭代中，我们将索引 mid 处的元素与索引 right 处的元素进行比较。
• 如果 nums[mid] > nums[right]，这表明枢轴点必须在 mid 的右侧。因为在（旋转之前的）排序数组中，枢轴右侧的所有元素都小于枢轴元素。如果 nums[mid] 大于 nums[right]，则意味着枢轴在 mid 的某个右侧位置，包括 mid 本身。
• 如果 nums[mid] <= nums[right]，则意味着枢轴点可能在 mid 处或在 mid 的左侧。这是因为在排序数组中，枢轴左侧的所有元素都大于枢轴元素。如果 nums[mid] 小于或等于 nums[right]，则表明枢轴可能在 mid 处或其左侧。

4. 更新指针

• 根据比较结果，我们相应地更新指针以缩小搜索空间：
• 如果 nums[mid] > nums[right]，我们将 left 更新为 mid + 1，因为我们知道枢轴在 mid 的右侧。
• 如果 nums[mid] <= nums[right]，我们将 right 更新为 mid，因为枢轴可能在 mid 处或在其左侧。

5. 收敛与返回

• 二分查找将继续进行，直到 left 和 right 收敛，即它们指向同一个元素。此时，left（或 right，它们在收敛时是相同的）代表数组中枢轴元素的索引。
• 我们将此索引作为 findPivot 函数的结果返回。

时间和空间复杂度

1. 时间复杂度分析

二分搜索

• 该函数使用二分查找算法来确定排序和旋转数组中的枢轴元素。
• 在二分查找的每次迭代中，搜索区域都会减半。
• 二分查找的最坏情况时间复杂度为 O(log N)，其中 N 是数组中的元素数量。
• 这是因为每一步都会将数组一分为二，从而实现搜索空间的指数级缩减。

搜索空间缩减

• 在每一步，该函数都会根据 (nums[mid]) > nums[right] 的情况将搜索空间减半。
• 如果 nums[mid] > nums[right]，则数组的右侧存在枢轴元素。
• 如果 nums[mid] <= nums[right]，则数组的左侧存在枢轴元素。
• 实现对数时间复杂度取决于这种缩减搜索空间的方法。

无需额外数据结构

• 该函数不使用任何其他数据结构，例如数组、列表或堆栈。
• 它不会根据输入大小动态分配内存。

2. 空间复杂度为常数

• 因此，它的空间复杂度为 O(1)，对于此函数来说是常数空间复杂度。
• 因此，对于此函数而言，所需的空间不随输入向量 nums 的大小而变化。

总之，findPivot 函数的时间复杂度为 O(log N)，空间复杂度为 O(1)，使其成为查找排序和旋转数组中枢轴点的有效算法。

用途

C++ 中旋转排序数组的枢轴点的几种用法。

1. 搜索：为了在旋转数组中高效地进行搜索，了解枢轴点至关重要。一旦数组被分成两个已排序的子数组，就可以分别对这些子数组进行二分查找，从而减少搜索时间。
2. 排序：枢轴点可用于将数组恢复到其初始排序顺序。通过将子数组旋转回其原始位置的技术，排序数组需要 O(N) 的时间复杂度，其中 N 是数组中包含的元素数量。
3. 数组操作：理解如何操作已确定枢轴点的数组非常重要。例如，如果需要将数组旋转回其原始顺序，我们可以参考给定的枢轴点，它将作为这种旋转的基础。
4. 算法设计：需要理解和操作枢轴点的各种问题，这些问题在涉及旋转排序数组的问题中很常见。正确的枢轴策略通常是任何成功解决此类问题的算法的核心。
5. 性能优化：利用关于枢轴点的信息可以优化旋转数组上的某些操作。一个例子是查找排序和旋转数组中的最大值或最小值；如果我们使用枢轴点的信息，此操作可能需要 O(log n) 的时间复杂度。

结论

总之，通过二分查找算法可以有效地解决旋转排序数组中的枢轴点问题。通过仔细地基于元素比较更新指针，可以将搜索区域缩小到以对数时间复杂度 (O(logN)) 找到枢轴点，其中 N 是数组中的元素数量。这种方法有效且实用，因为枢轴点信息对于搜索、排序或其他数组操作等至关重要。