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

🕗 发布于 2024-12-11 18:39 算法二分算法蓝桥杯 stl c++

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++算法感兴趣的朋友，让我们一起进步！

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

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

核心算法基础：二分查找是基础算法之一，掌握它体现了候选人对算法与数据结构的基本功。

高频考题：二分查找广泛应用于数组、查找树、搜索问题等，是面试中高频出现的考点。

优化能力考察：二分查找从 O(n) 提升到 O(log n)，展示了候选人对优化算法效率的理解。

逻辑与边界处理：面试官通过二分查找问题可以考察候选人对边界条件、循环终止、溢出问题的细致处理能力。

拓展性强：二分查找是许多复杂算法的核心（如变种二分、搜索区间、旋转数组查找），也是动态规划、分治法的基础。

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

前言：

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

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

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

1.1 二分查找的基本概念

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

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

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

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

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

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

题目描述：

2.1 算法思路：

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

初始化边界：
定义左右指针 left 和 right，分别指向数组的起点和终点。
二分查找：
- 计算中点索引 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]。
终止条件：当 left == right 时，区间收敛到一个点，该点即为峰值索引。
返回结果：
返回 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 注释说明

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

暴力解法思路

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

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 解析

遍历数组：我们从数组的第二个元素 i = 1 开始遍历，直到倒数第二个元素 i = arr.size() - 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 算法解析

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

3.3 时间与空间复杂度

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

3.4 补充（可看可不看）

3.4.1 暴力解法

暴力解法步骤

遍历数组：
- 从数组的第二个元素到倒数第二个元素，逐一检查每个元素是否大于其左右邻居。
判断条件：
- 如果 nums[i] > nums[i - 1] 且 nums[i] > nums[i + 1]，则该元素是峰值，返回其索引。
边界条件：
- 数组的首尾元素可以是峰值。例如，如果第一个元素 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 二分查找步骤

初始化：使用 left 和 right 指针，分别指向数组的开始和结束位置。
判断中间元素：每次计算中间位置 mid，并判断中间元素和右端元素的大小关系：
- 如果 nums[mid] > nums[right]：说明最小值在 mid 右侧。此时，将 left 更新为 mid + 1，继续在右半部分查找。
- 如果 nums[mid] <= nums[right]：说明最小值在 mid 左侧或 mid 就是最小值，因此将 right 更新为 mid。
退出条件：循环条件是 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 算法解析

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

4.3 时间与空间复杂度

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

4.4 补充（可看可不看）

4.4.1 暴力解法

暴力解法的核心思路是：

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

步骤：

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

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，直接返回该元素，因为它是唯一的元素。
- 如果数组没有旋转（即它是已经排好序的），则返回数组的第一个元素，因为它就是最小值。

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 算法解析

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

通过上述「二分查找在旋转排序数组中的应用」、「查找最小缺勤学生」及「寻找峰值元素」等例子，可以总结出二分查找算法的核心思想、应用场景和优化技巧。

二分查找是一种高效的算法，适用于处理有序数据或特定条件的数据结构，能够显著优化查找、定位问题的时间复杂度。通过灵活调整左右指针，可以快速缩小搜索范围，在处理查找类问题时，尤其是在大数据量的情况下，表现出强大的优势。

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

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

原文地址：https://blog.csdn.net/braveact/article/details/144272764

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14

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

文章目录

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

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

1.1 二分查找的基本概念

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

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

2.1 算法思路：

2.2 示例代码：

2.2.1 注释说明

2.2.2 代码示例运行说明

2.3 时间与空间复杂度

2.4 补充（可看可不看）

2.4.1 暴力解法

2.4.2 示例代码：

2.4.3 解析

2.4.4 时间与空间复杂度

2.5 总结：

3. 题目2：寻找峰值

3.1 算法思路：

3.2 示例代码：

3.2.1 算法解析

3.3 时间与空间复杂度

3.4 补充（可看可不看）

3.4.1 暴力解法

3.4.2 示例代码：

3.4.3 算法解析

3.4.4 时间与空间复杂度

3.4.5 总结:

3.5 总结

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

4.1 算法思路：

4.1.1 二分查找步骤

4.2 示例代码：

4.2.1 算法解析

4.3 时间与空间复杂度

4.4 补充（可看可不看）

4.4.1 暴力解法

4.4.2 示例代码：

4.4.3 算法解析

4.4.4 时间与空间复杂度

4.4.5 总结：

4.5 总结：

5. 题目4：点名

5.1 算法思路：

5.2 示例代码：

5.2.1 算法解析

5.3 时间与空间复杂度

5.4 补充（收获丰收）

5.4.1 哈希解法

5.4.2 位运算解法

5.4.3 等差求和公式解法

5.4.4 排序解法

5.4.5 总结：

6 总结：

7. 最后

相关文章