【优选算法篇】剥洋葱式探索：用二分查找精准定位答案（下篇）

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++算法感兴趣的朋友，让我们一起进步！

接上篇：【优选算法篇】寻找隐藏的宝藏：用二分查找打开算法世界的大门（上篇）-CSDN博客

引言：通过上篇文章带大家简单了解“二分查找算法”，小试牛刀。接下来将让大家感受一下二分查找在解题的妙处。

1. 核心算法基础：二分查找是基础算法之一，掌握它体现了候选人对算法与数据结构的基本功。
2. 高频考题：二分查找广泛应用于数组、查找树、搜索问题等，是面试中高频出现的考点。
3. 优化能力考察：二分查找从 O(n) 提升到 O(log n)，展示了候选人对优化算法效率的理解。
4. 逻辑与边界处理：面试官通过二分查找问题可以考察候选人对边界条件、循环终止、溢出问题的细致处理能力。
5. 拓展性强：二分查找是许多复杂算法的核心（如变种二分、搜索区间、旋转数组查找），也是动态规划、分治法的基础。

总结：掌握二分查找不仅能通过高频面试题，更能体现逻辑思维与优化能力，是提升算法竞争力的必备技能。

前言：

二分查找是经典算法之一，以其高效的 O(log n) 时间复杂度在解决有序数据的查找问题中备受推崇。然而，面试和实际开发中，二分查找的基本用法往往不能满足复杂场景的需求。本篇博客将从二分查找的基础出发，逐步深入到进阶场景，帮助你掌握其在实际问题中的灵活应用。

"二分查找进阶算法：从基础到高级场景的全面解析"

1. C++ 二分查找算法进阶详解

1.1 二分查找的基本概念

二分查找是一种针对有序数组进行快速查找的算法。其核心思想是每次将搜索范围缩小一半，直到找到目标值或范围为空。

1.2 二分查找的进阶应用适用于更复杂的查找问题，以下是几个典型场景：

1. 查找特定条件的最值：在满足某些条件的范围内，用二分查找寻找最大值或最小值。例如，在一个升序数组中找到第一个大于等于目标值的位置。
2. 搜索无序数据中的最优解：在一些单调性函数中，通过二分查找定位最优解。比如，最小化时间、成本等问题。
3. 应用于高效解决问题：如LeetCode中的「分割数组的最大值」、「Koko吃香蕉」等问题，通过二分配合验证函数缩小答案范围。
4. 扩展至二维问题：如在行列有序的矩阵中查找特定元素，可以通过二分同时操作行和列。

进阶场景往往结合数学、逻辑优化，提升算法效率。

2. 题目1：山脉数组的峰顶索引

题目链接：852. 山脉数组的峰顶索引 - 力扣（LeetCode）

题目描述：

2.1 算法思路：

该算法用于在一个符合“山峰数组”性质的数组中找到峰值的索引。山峰数组是指数组元素先严格递增后严格递减，且保证存在一个峰值。通过二分查找优化时间复杂度为 O(log⁡n)。

1. 初始化边界： 定义左右指针 left 和 right，分别指向数组的起点和终点。
2. 二分查找：
   • 计算中点索引 mid = left + (right - left) / 2。
   • 比较 arr[mid] 和 arr[mid + 1]：
     • 若 arr[mid] > arr[mid + 1]：说明峰值在左侧，包括 mid，缩小范围为 [left, mid]。
     • 若 arr[mid] < arr[mid + 1]：说明峰值在右侧，缩小范围为 [mid + 1, right]。
3. 终止条件： 当 left == right 时，区间收敛到一个点，该点即为峰值索引。
4. 返回结果： 返回 left（或 right），即为峰值所在的索引。

2.2 示例代码：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = arr.size() - 1; // 初始化左右指针，分别指向数组的起点和终点
        while (left < right) { // 当左右指针未相遇时，继续搜索
            int mid = left + (right - left) / 2; // 计算中点，避免直接加法可能导致的溢出
            if (arr[mid] > arr[mid + 1]) {
                // 如果当前元素比右侧元素大，说明峰值在左侧（包括 mid）
                right = mid; // 缩小右边界到 mid
            } else {
                // 如果当前元素比右侧元素小，说明峰值在右侧
                left = mid + 1; // 缩小左边界到 mid + 1
            }
        }
        // 最终 left 和 right 收敛到同一点，即峰值索引
        return left;
    }
};

2.2.1 注释说明

1. 初始化左右指针：left 和 right 分别指向数组的首尾。
2. 二分查找的条件：
   • 比较中点 mid 与其右侧的元素 mid + 1 的大小。
   • 如果 arr[mid] > arr[mid + 1]，说明峰值在左边（包括 mid），调整 right 为 mid。
   • 如果 arr[mid] < arr[mid + 1]，说明峰值在右边，调整 left 为 mid + 1。
3. 终止条件： 当 left == right 时，搜索区间收敛到单个元素，该元素即为峰值索引。
4. 时间复杂度： 每次搜索区间减半，时间复杂度为 O(log⁡n) 。
5. 空间复杂度： 无需额外空间，空间复杂度为 O(1) 。

2.2.2 代码示例运行说明

假设输入 arr = [0, 2, 1, 0]：

• 初始 left = 0, right = 3。
• 第一次迭代：
  • mid = 1, arr[mid] = 2, arr[mid + 1] = 1。
  • 因为 arr[mid] > arr[mid + 1]，收缩右边界：right = mid = 1。
• 第二次迭代：
  • mid = 0, arr[mid] = 0, arr[mid + 1] = 2。
  • 因为 arr[mid] < arr[mid + 1]，收缩左边界：left = mid + 1 = 1。
• 最终 left == right == 1，返回索引 1，即峰值索引。

2.3 时间与空间复杂度

• 时间复杂度： 每次搜索区间减半，时间复杂度为 O(log⁡n) 。
• 空间复杂度： 无需额外空间，空间复杂度为 O(1) 。

2.4 补充（可看可不看）

2.4.1 暴力解法

暴力解法思路

1. 遍历数组：从数组的第二个元素开始，逐一比较相邻的元素。
2. 寻找峰值：如果当前元素大于其相邻的前一个和后一个元素，那么这个元素就是峰值，返回其索引。
3. 终止条件：根据题目条件，数组一定是“山峰数组”，所以一定会有一个峰值，我们可以直接返回第一个找到的峰值。

2.4.2 示例代码：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        // 从数组的第二个元素开始检查
        for (int i = 1; i < arr.size() - 1; i++) {
            // 判断当前位置是否是峰值
            if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                return i;  // 找到峰值，返回索引
            }
        }
        return -1;  // 理论上永远不会执行到这行，因为数组是山峰数组
    }
};

2.4.3 解析

1. 遍历数组：我们从数组的第二个元素 i = 1 开始遍历，直到倒数第二个元素 i = arr.size() - 2（因为峰值不可能在数组的两端）。
2. 判断条件：对于每个元素 arr[i]，检查它是否大于其前一个元素 arr[i-1] 且大于其后一个元素 arr[i+1]。如果是，说明该元素就是峰值，返回其索引 i。

2.4.4 时间与空间复杂度

• 时间复杂度：遍历一次数组，因此时间复杂度为 O(n) ，其中 n 是数组的长度。
• 空间复杂度：只使用了常量空间，空间复杂度为 O(1) 。

2.5 总结：

二分查找是一种重要的算法，能够在 O(log⁡n) 时间内完成查找，适用于大规模数据的高效处理。

3. 题目2：寻找峰值

题目链接：162. 寻找峰值 - 力扣（LeetCode）

题目描述：

3.1 算法思路：

• 问题分析：
  • 峰值元素：一个数组中的元素，如果它大于相邻的两个元素，即为峰值元素。
  • 数组中保证至少有一个峰值元素，因此我们可以放心找到一个峰值元素，而不需要担心边界条件。
  • 峰值可能在数组的两端（即第一个或最后一个元素），也可能在数组的中间。
• 二分查找优化：
  • 由于数组是无序的，但是我们知道存在峰值元素，并且数组中的元素可能先递增后递减（或者其他模式），所以可以通过二分查找的方式来快速缩小查找范围。
  • 二分查找步骤：
    • 定义左右指针 left 和 right，并且不断缩小搜索区间直到找到一个峰值。
    • 每次选择中间元素 mid，然后比较 nums[mid] 和 nums[mid+1]：
      • 如果 nums[mid] > nums[mid+1]，说明可能的峰值在左侧（包括当前 mid），所以将右边界更新为 mid。
      • 如果 nums[mid] < nums[mid+1]，说明峰值可能在右侧，更新左边界为 mid + 1。
  • 最终，当 left 和 right 收敛时，left 即为峰值元素的索引。

3.2 示例代码：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;  // 初始化左右边界
        while (left < right) {  // 当左边界小于右边界时继续二分查找
            int mid = left + (right - left) / 2;  // 计算中间位置
            // 如果 mid 的元素大于 mid+1，峰值可能在左半边或是 mid
            if (nums[mid] > nums[mid + 1]) {
                right = mid;  // 收缩右边界
            } else {  // 如果 mid 的元素小于 mid+1，峰值可能在右半边
                left = mid + 1;  // 收缩左边界
            }
        }
        return left;  // 最终 left 和 right 会收敛到峰值的位置
    }
};

3.2.1 算法解析

1. 初始化：
   • left 和 right 指针分别初始化为数组的起始位置和结束位置。
2. 循环条件：
   • while (left < right)：只要左边界小于右边界，就继续进行二分查找。直到左边界和右边界重合时，退出循环。
3. 中间元素的计算：
   • int mid = left + (right - left) / 2：计算当前区间的中间位置，避免直接使用 (left + right) / 2 可能导致的溢出。
4. 判断峰值所在方向：
   • 如果 nums[mid] > nums[mid+1]：说明 mid 是可能的峰值或峰值在 mid 左侧，因此将右边界 right 更新为 mid。
   • 如果 nums[mid] < nums[mid+1]：说明峰值在 mid 右侧，因此将左边界 left 更新为 mid + 1。
5. 返回结果：
   • 最终，left 和 right 会收敛到同一个位置，即峰值元素的索引。

3.3 时间与空间复杂度

• 时间复杂度：每次查找将搜索区间缩小一半，因此时间复杂度为 O(log⁡n)，其中 n 是数组的长度。
• 空间复杂度：只使用了常数的额外空间，空间复杂度为 O(1)。

3.4 补充（可看可不看）

3.4.1 暴力解法

暴力解法步骤

1. 遍历数组：
   • 从数组的第二个元素到倒数第二个元素，逐一检查每个元素是否大于其左右邻居。
2. 判断条件：
   • 如果 nums[i] > nums[i - 1] 且 nums[i] > nums[i + 1]，则该元素是峰值，返回其索引。
3. 边界条件：
   • 数组的首尾元素可以是峰值。例如，如果第一个元素 nums[0] > nums[1]，则第一个元素是峰值；如果最后一个元素 nums[n-1] > nums[n-2]，则最后一个元素是峰值。

3.4.2 示例代码：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        // 如果数组长度为1，直接返回
        if (nums.size() == 1) {
            return 0;
        }
        
        // 遍历数组，从第二个元素到倒数第二个元素
        for (int i = 1; i < nums.size() - 1; i++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;  // 如果满足条件，返回索引
            }
        }
        
        // 边界情况：检查数组的首尾元素是否为峰值
        if (nums[0] > nums[1]) {
            return 0;  // 第一个元素是峰值
        }
        if (nums[nums.size() - 1] > nums[nums.size() - 2]) {
            return nums.size() - 1;  // 最后一个元素是峰值
        }
        
        return -1;  // 应该不会执行到这里，因为题目保证至少有一个峰值
    }
};

3.4.3 算法解析

• 基本思路：我们通过暴力遍历数组，检查每个元素是否大于其相邻的元素。如果是，则返回该元素的索引。对于数组的两端元素，我们单独检查它们是否大于唯一的相邻元素，如果是，则它们是峰值。
• 遍历过程：
  1. 中间元素的检查：遍历数组中的每个元素（除了第一个和最后一个），检查其是否比左右邻居都大。
  2. 边界元素的检查：首先检查数组的第一个和最后一个元素，看它们是否大于其唯一相邻元素。

3.4.4 时间与空间复杂度

• 时间复杂度：O(n)，需要遍历数组中的每个元素，因此时间复杂度为 O(n)，其中 n 是数组的长度。
• 空间复杂度：O(1)，我们只使用了常数的额外空间。

适用场景

• 适用于数组的规模较小的情况，因为其时间复杂度为 O(n)，当数组长度较大时，暴力解法的效率会较低。对于大规模数据，通常更推荐使用二分查找优化算法来解决。

3.4.5 总结:

暴力解法的优点是简单直观，易于理解和实现。虽然它的时间复杂度较高，为 O(n)，但在小规模数据上完全可行。如果你希望解决更大规模的数组问题，可以考虑采用二分查找优化算法。

3.5 总结

这个算法通过二分查找的方式高效地找到了峰值元素的索引，时间复杂度为 O(logn)，大大减少了暴力解法可能的性能瓶颈。其核心在于利用了数组的单调性，精确定位了峰值的范围，并根据比较结果逐步缩小查找范围，最终找到峰值。

4. 题目3：寻找旋转排序数组中的最小值

题目链接：153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

题目描述：

4.1 算法思路：

这个问题的关键是理解数组被旋转后的结构：原本升序的数组，在旋转后可能分成两个升序子数组，最小元素位于两个子数组之间的断点处。利用二分查找可以快速定位这个断点。

4.1.1 二分查找步骤

1. 初始化：使用 left 和 right 指针，分别指向数组的开始和结束位置。
2. 判断中间元素：每次计算中间位置 mid，并判断中间元素和右端元素的大小关系：
   • 如果 nums[mid] > nums[right]：说明最小值在 mid 右侧。此时，将 left 更新为 mid + 1，继续在右半部分查找。
   • 如果 nums[mid] <= nums[right]：说明最小值在 mid 左侧或 mid 就是最小值，因此将 right 更新为 mid。
3. 退出条件：循环条件是 left < right，当 left 和 right 收敛到相同位置时，left 就是最小元素的索引。

4.2 示例代码：

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;
            } 
            // 否则，最小值在左半部分（包含 mid）
            else {
                right = mid;
            }
        }
        // 最终 left 和 right 会重合，返回最小值
        return nums[left];
    }
};

4.2.1 算法解析

1. 初始化：
   • left = 0，指向数组的第一个元素。
   • right = nums.size() - 1，指向数组的最后一个元素。
2. 二分查找：
   • 计算中间位置 mid，然后与 right 位置的元素进行比较。
   • 如果 nums[mid] > nums[right]，说明最小值在右半部分，因此将 left = mid + 1。
   • 如果 nums[mid] <= nums[right]，说明最小值在左半部分（包括 mid），因此将 right = mid。
3. 终止条件：
   • 当 left 和 right 收敛（left == right）时，退出循环，此时 left 就是最小元素的索引，返回 nums[left]。

4.3 时间与空间复杂度

• 时间复杂度：O(log n)，每次都将搜索区间缩小一半，因此算法的时间复杂度是 O(log n)，这是二分查找的典型复杂度。
• 空间复杂度：O(1)，只使用了常数的额外空间。

4.4 补充（可看可不看）

4.4.1 暴力解法

暴力解法的核心思路是：

1. 遍历数组：直接遍历数组中的每个元素，找到最小值。
2. 找到最小元素：由于数组是旋转的，所以最小的元素必定是一个“拐点”，即比其前一个元素小。如果我们遍历整个数组，直接比较每个元素，就能找到最小的那个。

步骤：

1. 遍历数组中的每个元素，检查当前元素是否小于前一个元素。
2. 如果某个元素小于前一个元素，则该元素为最小值。
3. 特别地，如果数组没有旋转，那么第一个元素即为最小值。

4.4.2 示例代码：

class Solution {
public:
    int findMin(vector<int>& nums) {
        // 如果数组只有一个元素，直接返回
        if (nums.size() == 1) {
            return nums[0];
        }
        
        // 遍历数组，查找最小元素
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i - 1]) {
                return nums[i];  // 如果当前位置的元素小于前一个元素，则说明该元素为最小值
            }
        }
        
        // 如果没有找到旋转点，数组没有旋转，最小值为第一个元素
        return nums[0];
    }
};

4.4.3 算法解析

1. 遍历数组：
   • 从第二个元素开始遍历，逐个与前一个元素比较。
   • 如果当前元素小于前一个元素，那么当前元素就是最小值（即旋转点）。
2. 边界情况：
   • 如果数组的长度为1，直接返回该元素，因为它是唯一的元素。
   • 如果数组没有旋转（即它是已经排好序的），则返回数组的第一个元素，因为它就是最小值。

4.4.4 时间与空间复杂度

• 时间复杂度：
  • 最坏情况下，我们需要遍历整个数组一次，因此时间复杂度是 O(n)，其中 n 是数组的长度。
• 空间复杂度：
  • 我们只使用了常数的额外空间，所以空间复杂度是 O(1)。

适用场景

• 适用于较小的数组，或者当数组的旋转非常小（即接近未旋转的情况）时，暴力解法效果较好。
• 如果数组较大或需要多次查找，暴力解法的效率较低，建议使用二分查找方法来提高性能。

4.4.5 总结：

暴力解法的优点是实现简单，易于理解，适用于数据规模较小的情况。但由于它的时间复杂度是 O(n)，在处理大规模数组时，效率较低。在处理较大的旋转数组时，可以考虑使用二分查找方法来提升效率，达到 O(log n) 的时间复杂度。

4.5 总结：

• 通过利用旋转排序数组的特性，结合二分查找方法，能够在 O(log n) 时间复杂度内找到最小元素。
• 二分查找的关键是判断中间元素与右端元素的大小关系，从而决定搜索的方向。

5. 题目4：点名

题目链接：LCR 173. 点名 - 力扣（LeetCode）

题目描述：

5.1 算法思路：

• 问题分析：
  • 假设给定的 records 数组表示学生的出勤记录，且已按升序排列。
  • 目标：找出第一个缺勤学生的位置，即 records[i] != i 的最小索引。
  • 该数组中，若某个位置 i 对应的值 records[i] 大于 i，则说明从 i 到数组的末尾，后续学生都应该是出勤的。反之，如果某个位置 i 对应的值小于 i，则说明当前位置之前的学生一定是缺勤的。
• 二分查找：
  • 采用二分查找思想，通过不断缩小查找范围来寻找最小缺勤学生的位置。
  • 设定两个指针 left 和 right 分别指向数组的起始和结束位置。通过比较 records[mid] 和 mid 的大小关系来决定调整 left 和 right。
    • 如果 records[mid] == mid，表示该位置的学生出勤，说明最小缺勤学生的位置在右边（即 left = mid + 1）。
    • 如果 records[mid] != mid，说明可能存在缺勤学生，因此继续在左边查找（即 right = mid）。
  • 最终，当 left 和 right 重合时，检查这个位置的出勤情况，返回相应的结果。
• 边界情况：
  • 当 left 和 right 相等时，我们检查 records[left] 是否等于 left，如果是，则返回 left + 1，否则返回 left。

5.2 示例代码：

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0, right = records.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 如果 mid 对应的学生编号与索引匹配，则最小缺勤学生在右边
            if (records[mid] == mid) {
                left = mid + 1;
            }
            // 如果 mid 对应的学生编号与索引不匹配，则最小缺勤学生在左边
            else {
                right = mid;
            }
        }
        // 最终判断 left 和 right 指向的索引位置
        if (records[left] == left) return left + 1;
        else return left;
    }
};

5.2.1 算法解析

1. 初始化：
   • left = 0，right = records.size() - 1，指向数组的两端。
2. 二分查找：
   • 计算中间位置 mid = left + (right - left) / 2。
   • 如果 records[mid] == mid，表示该位置的学生出勤，更新 left = mid + 1，搜索右半部分。
   • 如果 records[mid] != mid，则更新 right = mid，继续在左半部分查找。
3. 退出条件：
   • 当 left == right 时，退出循环。
   • 最后检查 records[left] 与 left 是否匹配，返回相应的结果。
4. 返回值：
   • 如果 records[left] == left，说明此位置是出勤学生，返回 left + 1。
   • 否则返回 left，说明当前位置为缺勤学生。

5.3 时间与空间复杂度

• 时间复杂度：O(log n)，每次二分查找将查找范围缩小一半，因此时间复杂度为 O(log n)，其中 n 是数组的长度。
• 空间复杂度：O(1)，只使用了常数的额外空间。

适用场景

• 本问题适用于已排序的数组，通过二分查找来优化查找过程，避免了暴力遍历的 O(n) 时间复杂度，提升了查找效率。

5.4 补充（收获丰收）

除了使用二分查找来解决该问题外，还可以通过其他几种方法来实现。以下是四种常见的解法，包括哈希、位运算、等差求和公式等。

5.4.1 哈希解法

哈希解法是通过使用哈希集合来记录已经出现过的元素。我们可以遍历数组并查找缺失的元素。

思路：

• 利用哈希集合记录数组中已出现的元素。
• 遍历数组的每一个元素，如果该元素的值对应的索引没有出现过，说明该索引即为缺失的最小值。

示例代码：

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        unordered_set<int> recordSet;
        for (int i = 0; i < records.size(); i++) {
            recordSet.insert(records[i]);
        }
        
        for (int i = 0; i < records.size(); i++) {
            if (recordSet.find(i) == recordSet.end()) {
                return i;  // 返回缺失的最小值
            }
        }
        return records.size();  // 如果没有缺失值，则返回数组的长度
    }
};

时间复杂度：

• 遍历一次数组插入哈希表，时间复杂度为 O(n)。
• 查找缺失元素的时间复杂度为 O(n)。
• 总体时间复杂度为 O(n)。

空间复杂度：

• 需要 O(n) 的额外空间来存储哈希表。

5.4.2 位运算解法

位运算解法利用异或（XOR）运算的特性来实现。异或的特性是：

• a ^ a = 0
• a ^ 0 = a

思路：

• 用一个变量存储所有索引和数组元素的异或结果。由于异或相同的值会互相抵消（即 x ^ x = 0），最后剩下的就是缺失的最小值。

示例代码：

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int result = 0;
        for (int i = 0; i < records.size(); i++) {
            result ^= i ^ records[i];  // 将索引和元素进行异或
        }
        return result == records.size() ? result : result + 1;  // 返回缺失的值
    }
};

时间复杂度：

• 时间复杂度为 O(n)，我们遍历一次数组进行异或运算。

空间复杂度：

• 空间复杂度为 O(1)，只使用了常量空间。

5.4.3 等差求和公式解法

通过利用等差数列求和公式来找到缺失的最小元素。

思路：

• 数组的元素在理想情况下应该是连续的 0 到 n-1，利用等差数列求和公式 sum = n * (n-1) / 2 来计算理论上的数组元素和。
• 然后计算数组实际的元素和。两者的差值即为缺失的最小值。

示例代码：

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int n = records.size();
        int expectedSum = (n * (n - 1)) / 2;  // 等差数列求和公式
        int actualSum = 0;
        
        for (int i = 0; i < records.size(); i++) {
            actualSum += records[i];
        }
        
        return expectedSum - actualSum;
    }
};

时间复杂度：

• 时间复杂度为 O(n)，我们需要遍历数组来计算实际和。

空间复杂度：

• 空间复杂度为 O(1)，只使用了常量空间。

5.4.4 排序解法

通过先对数组进行排序，然后遍历数组找到最小的缺失元素。

思路：

• 首先对数组进行排序。
• 然后从数组的第一个元素开始检查，查看哪个索引位置的元素不等于索引值，找到第一个不匹配的位置，即为缺失的最小值。

示例代码：

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        sort(records.begin(), records.end());  // 对数组进行排序
        
        for (int i = 0; i < records.size(); i++) {
            if (records[i] != i) {
                return i;  // 返回缺失的最小值
            }
        }
        return records.size();  // 如果没有缺失值，返回数组的长度
    }
};

时间复杂度：

• 时间复杂度为 O(n log n)，由于排序的时间复杂度是 O(n log n)。

空间复杂度：

• 空间复杂度为 O(1) 或 O(n)，取决于使用的排序算法。

5.4.5 总结：

• 哈希解法：通过哈希表记录已出现的元素，时间复杂度 O(n)，空间复杂度 O(n)。
• 位运算解法：利用异或运算的特性进行求解，时间复杂度 O(n)，空间复杂度 O(1)。
• 等差求和公式解法：通过计算数组的理论和与实际和的差值来找到缺失的最小元素，时间复杂度 O(n)，空间复杂度 O(1)。
• 排序解法：通过排序数组然后遍历查找缺失的元素，时间复杂度 O(n log n)，空间复杂度 O(1) 或 O(n)。

建议：每种方法都有其优缺点，具体选择哪种解法取决于题目的限制条件和数据规模。

6 总结：

通过二分查找，可以在 O(log n) 时间内找出最小缺勤学生的位置。二分查找的核心在于通过比较 records[mid] 和 mid 来逐步缩小搜索范围，最终确定缺勤学生的位置。这种方法能够显著提高查找效率，特别是在大规模数据集上。

7. 最后

通过上述「二分查找在旋转排序数组中的应用」、「查找最小缺勤学生」及「寻找峰值元素」等例子，可以总结出二分查找算法的核心思想、应用场景和优化技巧。 二分查找是一种高效的算法，适用于处理有序数据或特定条件的数据结构，能够显著优化查找、定位问题的时间复杂度。通过灵活调整左右指针，可以快速缩小搜索范围，在处理查找类问题时，尤其是在大数据量的情况下，表现出强大的优势。

路虽远，行则将至；事虽难，做则必成

亲爱的读者们，下一篇文章再会！！！