【优选算法篇】在旋转与缺失间寻踪：二分查找的妙趣演绎

C++ 二分查找进阶：从理论到实践的深入解析

前言

接上篇【优选算法篇】在分割中追寻秩序：二分查找的智慧轨迹

二分查找不仅是一种高效的算法，它的背后更蕴含了数据分割的哲学与思维方式。通过有序的分割，我们得以在庞大的数据世界中迅速锁定答案。而在这篇进阶解析中，我们将不仅仅停留于基本的二分查找，更会带你深入其在复杂场景中的应用，让你全面掌握这项重要的算法工具。

第二章：进阶练习

1.1 山峰数组的峰顶

题目链接：852. 山脉数组的峰顶索引

题目描述：

符合下列属性的数组 arr 称为山脉数组：

• arr.length >= 3
• 存在索引 i（0 < i < arr.length - 1），使得：
  • arr[0] < arr[1] < ... < arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给定一个由整数组成的山脉数组 arr，返回其峰顶索引 i，即满足条件 arr[i] 是整个数组中最大的元素，并且左右两边的数据呈现先升后降的趋势。

示例 1：

• 输入：arr = [0,1,0]
• 输出：1

示例 2：

• 输入：arr = [0,2,1,0]
• 输出：1

示例 3：

• 输入：arr = [24,69,100,99,79,78,67,36,26,19]
• 输出：2

提示：

• 3 <= arr.length <= 104
• 0 <= arr[i] <= 106
• 题目保证 arr 是山脉数组。

解题思路

要找到山脉数组的峰顶索引，我们可以采用暴力查找和二分查找两种方法。

1. 暴力查找：遍历数组，找到一个比左右相邻元素都大的数，即为峰顶索引。
2. 二分查找：利用数组的上升和下降趋势，快速定位峰顶。

1.1.1 暴力查找

算法思路：

1. 遍历数组中的每个元素，判断其是否比左右相邻的元素都大。
2. 一旦找到符合条件的元素，返回其索引即可。

C++代码实现：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int n = arr.size();
        for (int i = 1; i < n - 1; i++) {
            if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                return i; // 找到峰顶，返回索引
            }
        }
        return -1; // 为了应对OJ题目，所有路径必须有返回值
    }
};

1.1.2 二分查找

算法思路：

1. 峰顶索引 i 的特点是：arr[i] > arr[i - 1] && arr[i] > arr[i + 1]。但如果我们只根据 arr[i] 与两边的元素大小关系进行分析，可以通过二分查找快速定位峰顶。
2. 如果 arr[mid] > arr[mid - 1]，说明在上升趋势中，峰顶可能在右侧，因此 left = mid。
3. 如果 arr[mid] < arr[mid - 1]，说明在下降趋势中，峰顶可能在左侧，因此 right = mid - 1。

C++代码实现：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] > arr[mid - 1]) {
                left = mid;  // 峰顶在右侧（包括mid）
            } else {
                right = mid - 1;  // 峰顶在左侧
            }
        }
        return left;  // 返回峰顶索引
    }
};

图解分析

假设数组为 arr = [0,2,1,0]，我们通过二分查找找到峰顶：

1. 初始状态：
   • left = 1，right = 2。
   • 中间位置 mid = (1 + 2 + 1) / 2 = 2，此时 arr[mid] = 1。
   • 因为 arr[mid] < arr[mid - 1]，所以更新 right = mid - 1 = 1。
2. 结束状态：
   • 此时 left == right == 1，因此峰顶索引为 1，返回 1。

易错点提示：

1. 数组边界处理：注意从索引 1 到 n-2 进行查找，防止越界情况。
2. 二分查找的区间判断：根据 mid 所处的上升或下降趋势，合理缩小查找区间，避免遗漏峰顶。

代码解读：

• 时间复杂度：二分查找每次将查找范围缩小一半，因此时间复杂度为 O(log n)。
• 空间复杂度：仅使用常数级额外空间，空间复杂度为 O(1)。

1.2 寻找峰值

题目链接：162. 寻找峰值

题目描述：

峰值元素是指其值严格大于左右相邻元素的元素。给定一个整数数组 nums，找到任意一个峰值元素并返回其索引。你可以假设 nums[-1] = -∞ 和 nums[n] = -∞，即数组两端可以视为负无穷。

要求实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

• 输入：nums = [1,2,3,1]
• 输出：2
• 解释：3 是峰值元素，返回其索引 2。

示例 2：

• 输入：nums = [1,2,1,3,5,6,4]
• 输出：1 或 5
• 解释：函数可以返回索引 1（峰值元素为 2），或返回索引 5（峰值元素为 6）。

提示：

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 数组中的所有元素 nums[i] 均不同。

解题思路

我们可以利用二分查找来高效地找到数组中的峰值元素。通过比较当前元素与其相邻元素，我们可以推断峰值所在的方向。

• 如果 nums[i] > nums[i + 1]，则峰值位于数组左侧，因为右边的元素比当前元素小。
• 如果 nums[i] < nums[i + 1]，则峰值位于数组右侧，因为右边的元素比当前元素大。
• 使用这种分段性，可以在 O(log n) 的时间复杂度内，通过二分查找找到峰值。

1.2.1 二分查找

算法步骤：

1. 初始化左右指针：
   • left 指向数组的起始位置，right 指向数组的末尾位置。
2. 进行二分查找：
   • 计算中间位置 mid = left + (right - left) / 2。
   • 如果 nums[mid] > nums[mid + 1]，说明峰值在左侧或当前位置，因此更新 right = mid。
   • 如果 nums[mid] < nums[mid + 1]，说明峰值在右侧，因此更新 left = mid + 1。
3. 结束条件：当 left == right 时，返回 left 或 right 即为峰值元素的索引。

C++代码实现：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;  // 峰值在左侧或当前位置
            } else {
                left = mid + 1;  // 峰值在右侧
            }
        }
        
        return left;  // 最终 left == right
    }
};

图解分析

假设数组为 nums = [1,2,1,3,5,6,4]，我们通过二分查找找到峰值：

1. 初始状态：
   • left = 0, right = 6。
   • 计算 mid = (0 + 6) / 2 = 3，此时 nums[mid] = 3，nums[mid + 1] = 5。
   • 因为 nums[mid] < nums[mid + 1]，更新 left = mid + 1 = 4。
2. 步骤 1：
   • left = 4, right = 6。
   • 计算 mid = (4 + 6) / 2 = 5，此时 nums[mid] = 6，nums[mid + 1] = 4。
   • 因为 nums[mid] > nums[mid + 1]，更新 right = mid = 5。
3. 结束状态：
   • 此时 left == right == 5，返回 5 作为峰值索引。

易错点提示：

1. 数组边界处理：因为假设了 nums[-1] = nums[n] = -∞，所以无需处理越界情况。
2. 二分查找的区间更新：注意根据中间元素与相邻元素的大小关系，正确更新左右指针，避免遗漏峰值。

代码解读：

• 时间复杂度：每次查找都会将查找范围缩小一半，因此时间复杂度为 O(log n)。
• 空间复杂度：仅使用常数级额外空间，空间复杂度为 O(1)。

1.3 搜索旋转排序数组中的最小值

题目链接：153. 搜索旋转排序数组中的最小值

题目描述：

给定一个按升序排列的整数数组 nums，数组中的值互不相同。数组在传递给函数之前，在某个未知的下标 k（0 <= k < nums.length）上进行了旋转，使得数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] 的形式。

请找出旋转后数组中的最小值。

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

示例 1：

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

示例 2：

• 输入：nums = [3,4,5,1,2]
• 输出：1

示例 3：

• 输入：nums = [11,13,15,17]
• 输出：11

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• 数组中的所有整数互不相同
• 数组已按升序排列，并进行了旋转

解题思路

由于数组是经过旋转后的升序数组，因此最小值在数组中有明确的特征：它位于某个旋转点。为了实现 O(log n) 的时间复杂度，我们可以通过二分查找来锁定旋转点的位置，并找到最小值。

我们可以通过比较中间元素与数组的末尾元素来判断当前的中间位置是在数组的左半部分（较大部分）还是右半部分（较小部分）。

• 如果 nums[mid] > nums[right]，说明最小值在右半部分。
• 如果 nums[mid] <= nums[right]，说明最小值在左半部分或当前 mid 位置。

1.3.1 二分查找算法分析

算法步骤：

1. 初始化左右指针：
   • left 指向数组的起始位置，right 指向数组的末尾位置。
2. 进行二分查找：
   • 计算中间位置 mid = left + (right - left) / 2。
   • 如果 nums[mid] > nums[right]，说明最小值在右侧，更新 left = mid + 1。
   • 如果 nums[mid] <= nums[right]，说明最小值在左侧或 mid 位置，更新 right = mid。
3. 结束条件：当 left == right 时，left 指向的就是最小值。

C++代码实现：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;  // 最小值在右半部分
            } else {
                right = mid;  // 最小值在左半部分或 mid 位置
            }
        }
        return nums[left];  // left 指向最小值
    }
};

图解分析

假设数组为 nums = [4,5,6,7,0,1,2]，我们通过二分查找找到最小值：

1. 初始状态：
   • left = 0, right = 6。
   • 计算 mid = (0 + 6) / 2 = 3，此时 nums[mid] = 7，nums[right] = 2。
   • 因为 nums[mid] > nums[right]，更新 left = mid + 1 = 4。
2. 步骤 1：
   • left = 4, right = 6。
   • 计算 mid = (4 + 6) / 2 = 5，此时 nums[mid] = 1，nums[right] = 2。
   • 因为 nums[mid] <= nums[right]，更新 right = mid = 5。
3. 步骤 2：
   • left = 4, right = 5。
   • 计算 mid = (4 + 5) / 2 = 4，此时 nums[mid] = 0，nums[right] = 1。
   • 因为 nums[mid] <= nums[right]，更新 right = mid = 4。
4. 结束状态：
   • 此时 left == right == 4，返回 nums[left] = 0。

易错点提示：

1. 旋转数组的理解：旋转后的数组可以分为两部分，一部分较大，另一部分较小。我们通过二分查找来判断中间位置在哪个部分，从而锁定最小值。
2. 区间收缩的正确性：注意 nums[mid] <= nums[right] 的条件下，right 可以等于 mid，因为此时 mid 可能是最小值。
3. 这道题是严格升序，若有相同的值，需要针对相同的值的情况进行去重，代码是有更改的！

代码解读：

• 时间复杂度：每次查找都会将查找范围缩小一半，因此时间复杂度为 O(log n)。
• 空间复杂度：仅使用常数级额外空间，空间复杂度为 O(1)。

1.4 0～n-1 中缺失的数字

题目链接：剑指 Offer 53 - II. 0～n-1 中缺失的数字

这题现在改了个名字，叙述也变了：某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。 不过意思都是一样的哈

题目描述：

一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0～n-1 之内。在范围 0～n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1：

• 输入：[0,1,3]
• 输出：2

示例 2：

• 输入：[0,1,2,3,4,5,6,7,9]
• 输出：8

提示：

• 1 <= 数组长度 <= 10000

解题思路

在这个递增排序的数组中，我们可以利用其规律性来设计一个二分查找算法，使得查找缺失数字的时间复杂度降低到 O(log n)。

在数组中，我们发现：

• 在缺失数字的左侧，数组中的元素值等于其下标。
• 在缺失数字的右侧，数组中的元素值大于其下标。

因此，缺失位置将数组划分为两个部分，具有明显的二段性。利用这个特性，我们可以通过二分查找来快速确定缺失的位置。

1.4.1 二分查找算法分析

算法步骤：

1. 初始化左右指针：
   • left 指向数组的起始位置，right 指向数组的末尾位置。
2. 进行二分查找：
   • 计算中间位置 mid = left + (right - left) / 2。
   • 如果 nums[mid] == mid，说明缺失数字在右侧部分，更新 left = mid + 1。
   • 如果 nums[mid] != mid，说明缺失数字在左侧部分或当前 mid 位置，更新 right = mid。
3. 结束条件：当 left == right 时，查找结束，此时 left 指向缺失的数字位置。

C++代码实现：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == mid) {
                left = mid + 1;  // 缺失数字在右半部分
            } else {
                right = mid;  // 缺失数字在左半部分
            }
        }
        
        // 返回缺失数字
        return left == nums[left] ? left + 1 : left;
    }
};

图解分析

假设数组为 nums = [0,1,3]，我们通过二分查找找到缺失的数字：

1. 初始状态：
   • left = 0, right = 2。
   • 计算 mid = (0 + 2) / 2 = 1，此时 nums[mid] = 1。
   • 因为 nums[mid] == mid，更新 left = mid + 1 = 2。
2. 结束状态：
   • 此时 left == right == 2，并且 nums[left] = 3。
   • 根据条件 left == nums[left] 不满足，返回缺失的数字 left = 2。

易错点提示：

1. 边界条件：当 left == right 时，还需要判断 nums[left] 是否等于 left，从而确定最终的缺失数字。
2. 查找方向的判断：当 nums[mid] == mid 时，说明左侧部分是完整的，因此需要查找右半部分。

代码解读：

• 时间复杂度：每次查找都会将查找范围缩小一半，因此时间复杂度为 O(log n)。
• 空间复杂度：仅使用常数级额外空间，空间复杂度为 O(1)。

写在最后

二分查找的世界远不止表面的“分割与查找”，更是对数据结构的深刻理解。在旋转数组中，二分查找的思想得以应用并拓展，让我们不仅感受到了算法的威力，还体会到了它背后精密的逻辑与哲思。在本篇进阶解析中，我们重点剖析了二分查找在复杂问题中的应用，期望各位能在更多场景中灵活运用这项基本而深刻的算法工具。