目录

一、704. 二分查找 - 力扣（LeetCode）

运行代码：

 1. 核心思想

2. 代码思路

初始化

循环条件

计算中间位置

比较中间值与目标值

未找到目标值

3. 关键点

4. 示例

二、34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

运行代码： 

1. 核心思想

2. 代码思路

边界情况处理

第一次二分查找：查找起始位置（左端点）

第二次二分查找：查找结束位置（右端点）

3. 关键点

4. 示例

5. 代码总结

超级重点：

1. 第一次二分查找：查找起始位置（左端点）

目标

实现逻辑

为什么这样设计？

示例

2. 第二次二分查找：查找结束位置（右端点）

目标

实现逻辑

为什么这样设计？

示例

3. 总结两次二分查找的差异

4. 为什么不能统一写法？

5. 示例分析

6. 结论

三、35. 搜索插入位置 - 力扣（LeetCode）

运行代码： 

1. 核心思想

2. 代码思路

初始化

二分查找

循环结束后的处理

3. 关键点

4. 示例

示例 1：

示例 2：

示例 3：

四、69. x 的平方根 - 力扣（LeetCode）

方法一：暴力查找

运行代码： 

方法二：二分查找算法

运行代码：

1. 边界情况处理

2. 二分查找

3. 循环查找

4. 终止条件

5. 返回结果

总结

五、852. 山脉数组的峰顶索引 - 力扣（LeetCode）

运行代码： 

1. 初始化指针

2. 二分查找循环

3. 返回结果

关键点解析

示例验证

复杂度

六、162. 寻找峰值 - 力扣（LeetCode）

运行代码： 

1. 初始化指针

2. 二分查找循环

3. 返回结果

关键点解析

示例验证

复杂度

七、153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

 运行代码：

1. 初始化指针

2. 二分查找循环

3. 返回结果

关键点解析

示例验证

复杂度

八、LCR 173. 点名 - 力扣（LeetCode）

运行代码： 

1. 初始化指针

2. 二分查找循环

3. 返回结果

关键点解析

示例验证

复杂度

---

一、704. 二分查找 - 力扣（LeetCode）

运行代码：

class Solution {
public:int search(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<=right){int mid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid-1;}else{return mid;}}return -1;}
};

 1. 核心思想

二分查找的核心思想是通过分治策略，每次将搜索区间缩小一半，从而快速定位目标值。它的时间复杂度是 O(log n)，效率非常高。

---

2. 代码思路

初始化

• left 和 right 分别表示当前搜索区间的左右边界。

  • left = 0：初始左边界，指向数组的第一个元素。

  • right = nums.size() - 1：初始右边界，指向数组的最后一个元素。

循环条件

• while (left <= right)：

  • 当 left <= right 时，说明当前搜索区间仍然有效，可以继续查找。

  • 如果 left > right，说明搜索区间已经无效，目标值不存在，退出循环并返回 -1。

计算中间位置

• int mid = left + (right - left) / 2：

  • 计算当前区间的中间位置 mid。

  • 使用 left + (right - left) / 2 而不是 (left + right) / 2，是为了避免 left + right 可能导致的整数溢出问题。

比较中间值与目标值

• if (nums[mid] < target)：

  • 如果中间值小于目标值，说明目标值在右半部分，更新左边界 left = mid + 1。

• else if (nums[mid] > target)：

  • 如果中间值大于目标值，说明目标值在左半部分，更新右边界 right = mid - 1。

• else：

  • 如果中间值等于目标值，说明找到了目标值，直接返回 mid（目标值的索引）。

未找到目标值

• 如果循环结束仍未找到目标值，返回 -1，表示目标值不存在于数组中。

---

3. 关键点

1. 有序数组：

   • 二分查找的前提是数组必须是有序的（升序或降序）。如果数组无序，需要先排序。

2. 区间更新：

   • 每次比较后，区间会被缩小一半：

     • 如果 nums[mid] < target，目标值在右半部分，更新 left = mid + 1。

     • 如果 nums[mid] > target，目标值在左半部分，更新 right = mid - 1。

3. 循环条件：

   • left <= right 确保在 left == right 时仍然检查最后一个可能的元素。

4. 返回值：

   • 找到目标值时返回其索引。

   • 未找到时返回 -1。

---

4. 示例

假设数组为 [1, 2, 3, 4, 5]，目标值为 4：

1. 初始区间：left = 0，right = 4。

2. 第一次循环：

   • mid = 2，nums[mid] = 3。

   • 3 < 4，更新 left = 3。

3. 第二次循环：

   • mid = 3，nums[mid] = 4。

   • 找到目标值，返回 3。

二、34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

运行代码： 

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {// 处理边界情况if (nums.size() == 0)return {-1, -1};int begin = 0;// 1. ⼆分左端点int left = 0, right = nums.size() - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1;elseright = mid;}// 判断是否有结果if (nums[left] != target)return {-1, -1};elsebegin = left; // 标记⼀下左端点// 2. ⼆分右端点left = 0, right = nums.size() - 1;while (left < right) {int mid = left + (right - left + 1) / 2;if (nums[mid] <= target)left = mid;elseright = mid - 1;}return {begin, right};}
};

1. 核心思想

• 使用两次二分查找：

  1. 第一次二分查找目标值的起始位置（左端点）。

  2. 第二次二分查找目标值的结束位置（右端点）。

• 通过两次二分查找，可以高效地找到目标值的区间范围。

---

2. 代码思路

边界情况处理

• 如果数组为空（nums.size() == 0），直接返回 {-1, -1}，因为目标值不可能存在于空数组中。

第一次二分查找：查找起始位置（左端点）

• 初始化：

  • left = 0，right = nums.size() - 1。

• 循环条件：

  • while (left < right)：当 left == right 时，退出循环。

• 计算中间位置：

  • int mid = left + (right - left) / 2。

• 比较中间值与目标值：

  • 如果 nums[mid] < target，说明目标值在右半部分，更新 left = mid + 1。

  • 否则（nums[mid] >= target），说明目标值在左半部分或当前位置就是起始位置，更新 right = mid。

• 判断是否找到目标值：

  • 如果 nums[left] != target，说明目标值不存在，返回 {-1, -1}。

  • 否则，记录起始位置 begin = left。

第二次二分查找：查找结束位置（右端点）

• 初始化：

  • left = 0，right = nums.size() - 1。

• 循环条件：

  • while (left < right)：当 left == right 时，退出循环。

• 计算中间位置：

  • int mid = left + (right - left + 1) / 2：

    • 这里 +1 是为了避免死循环（当 left 和 right 相邻时，mid 会偏向右侧）。

• 比较中间值与目标值：

  • 如果 nums[mid] <= target，说明目标值在右半部分或当前位置就是结束位置，更新 left = mid。

  • 否则（nums[mid] > target），说明目标值在左半部分，更新 right = mid - 1。

• 返回结果：

  • 返回 {begin, right}，其中 begin 是起始位置，right 是结束位置。

---

3. 关键点

1. 两次二分查找：

   • 第一次查找目标值的起始位置。

   • 第二次查找目标值的结束位置。

2. 查找起始位置：

   • 当 nums[mid] >= target 时，更新 right = mid，因为目标值可能在左半部分或当前位置就是起始位置。

3. 查找结束位置：

   • 当 nums[mid] <= target 时，更新 left = mid，因为目标值可能在右半部分或当前位置就是结束位置。

   • 计算 mid 时 +1，是为了避免死循环。

4. 边界条件：

   • 如果数组为空，直接返回 {-1, -1}。

   • 如果第一次二分查找未找到目标值，直接返回 {-1, -1}。

---

4. 示例

假设数组为 [5, 7, 7, 8, 8, 10]，目标值为 8：

1. 第一次二分查找（起始位置）：

   • 初始区间：left = 0，right = 5。

   • 第一次循环：

     • mid = 2，nums[mid] = 7。

     • 7 < 8，更新 left = 3。

   • 第二次循环：

     • mid = 4，nums[mid] = 8。

     • 8 >= 8，更新 right = 4。

   • 第三次循环：

     • left == right，退出循环。

   • 检查 nums[left] == 8，记录起始位置 begin = 3。

2. 第二次二分查找（结束位置）：

   • 初始区间：left = 0，right = 5。

   • 第一次循环：

     • mid = 3，nums[mid] = 8。

     • 8 <= 8，更新 left = 3。

   • 第二次循环：

     • mid = 4，nums[mid] = 8。

     • 8 <= 8，更新 left = 4。

   • 第三次循环：

     • mid = 5，nums[mid] = 10。

     • 10 > 8，更新 right = 4。

   • 退出循环，返回 {3, 4}。

---

5. 代码总结

这是一种高效且经典的解决有序数组中查找目标值区间的方法，时间复杂度为 O(log n)。

超级重点：

1. 第一次二分查找：查找起始位置（左端点）

目标

找到数组中第一个等于 target 的位置。

实现逻辑

• 中间值计算：
  mid = left + (right - left) / 2
  这种计算方式让 mid 偏向左侧（例如，当 left=3, right=4 时，mid=3）。

• 区间更新规则：

  • 如果 nums[mid] < target：
    说明目标值的起始位置在右半部分，更新 left = mid + 1。

  • 如果 nums[mid] >= target：
    说明目标值的起始位置可能在当前位置或左半部分，更新 right = mid。

为什么这样设计？

• 偏向左侧的 mid：
  确保在 nums[mid] == target 时，继续向左搜索更小的起始位置。

• 终止条件 left == right：
  最终 left 和 right 会收敛到第一个等于 target 的位置。

示例

数组 [5,7,7,8,8,10]，target=8：

• 初始区间 [0,5]，mid=2（值为7），7 < 8 → 更新 left=3。

• 新区间 [3,5]，mid=4（值为8），8 >= 8 → 更新 right=4。

• 循环结束，left=3，找到起始位置。

---

2. 第二次二分查找：查找结束位置（右端点）

目标

找到数组中最后一个等于 target 的位置。

实现逻辑

• 中间值计算：
  mid = left + (right - left + 1) / 2
  这种计算方式让 mid 偏向右侧（例如，当 left=3, right=4 时，mid=4）。

• 区间更新规则：

  • 如果 nums[mid] <= target：
    说明目标值的结束位置可能在当前位置或右半部分，更新 left = mid。

  • 如果 nums[mid] > target：
    说明目标值的结束位置在左半部分，更新 right = mid - 1。

为什么这样设计？

• 偏向右侧的 mid：
  确保在 nums[mid] == target 时，继续向右搜索更大的结束位置。

• +1 的作用：
  避免死循环。例如，当 left=3 和 right=4 时，若 mid=3，且 nums[mid] <= target，会导致无限循环（left=3 不变）。
  通过 mid = left + (right - left + 1)/2，mid 会取 4，从而打破循环。

示例

数组 [5,7,7,8,8,10]，target=8：

• 初始区间 [0,5]，mid=3（值为8），8 <= 8 → 更新 left=3。

• 新区间 [3,5]，mid=4（值为8），8 <= 8 → 更新 left=4。

• 新区间 [4,5]，mid=5（值为10），10 > 8 → 更新 right=4。

• 循环结束，right=4，找到结束位置。

---

3. 总结两次二分查找的差异

步骤	第一次查找（左端点）	第二次查找（右端点）
目标	找到第一个等于 target 的位置	找到最后一个等于 target 的位置
中间值计算	mid = left + (right - left) / 2	mid = left + (right - left + 1) / 2
偏向方向	偏向左侧	偏向右侧
更新规则	if (nums[mid] < target) → 右移	if (nums[mid] <= target) → 右移
防止死循环	无需 +1	需要 +1 避免无限循环

        防止死循环的方法：主要看right这个下标，如果这个下标有减1的话，就会加上1；反之如果没有，就不用加上。 （在求 mid 的时候，只有 right - 1 的情况下，才会向上取整（也就是 +1 取中间数） ）

---

4. 为什么不能统一写法？

• 目标不同：
  查找左端点时，需要尽可能向左收缩区间；查找右端点时，需要尽可能向右收缩区间。

• 中间值偏向性：
  偏向左侧或右侧的 mid 计算方式，是为了避免跳过目标值的边界位置。

• 循环终止条件：
  两次查找均使用 left < right，但不同的更新逻辑确保最终收敛到正确位置。

---

5. 示例分析

以数组 [5,7,7,8,8,8,10]，target=8 为例：

1. 第一次查找（左端点）：

   • 逐步收缩到第一个 8 的位置 3。

2. 第二次查找（右端点）：

   • 逐步收缩到最后一个 8 的位置 5。

如果两次查找使用相同的逻辑，可能会导致错误的结果或死循环。

---

6. 结论

        两次二分查找的差异是为了处理不同的边界方向（左/右端点），通过调整中间值的偏向性和区间更新规则，确保高效且准确地定位目标值的区间范围。这是二分查找在处理边界问题时的一种经典技巧。

三、35. 搜索插入位置 - 力扣（LeetCode）

运行代码： 

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1;elseright = mid;}if (nums[left] < target)return right + 1;return right;}
};

1. 核心思想

• 使用二分查找来定位目标值的位置。

• 如果目标值不存在，返回它应该被插入的位置。

---

2. 代码思路

初始化

• left = 0：初始左边界，指向数组的第一个元素。

• right = nums.size() - 1：初始右边界，指向数组的最后一个元素。

二分查找

• 循环条件：while (left < right)
  当 left == right 时，退出循环。

• 计算中间位置：
  int mid = left + (right - left) / 2
  这种计算方式避免整数溢出。

• 比较中间值与目标值：

  • 如果 nums[mid] < target：
    说明目标值在右半部分，更新 left = mid + 1。

  • 否则（nums[mid] >= target）：
    说明目标值在左半部分或当前位置就是目标值，更新 right = mid。

循环结束后的处理

• 循环结束后，left 和 right 指向同一个位置。

• 检查 nums[left] 与 target 的关系：

  • 如果 nums[left] < target：
    说明目标值应该插入到 right + 1 的位置。

  • 否则：
    说明目标值已经存在于数组中，返回 right（即目标值的索引）。

---

3. 关键点

1. 循环条件：

   • while (left < right)：当 left == right 时，退出循环。

   • 这种条件确保在循环结束时，left 和 right 指向同一个位置。

2. 中间值计算：

   • mid = left + (right - left) / 2：避免整数溢出。

3. 区间更新规则：

   • 如果 nums[mid] < target，更新 left = mid + 1。

   • 如果 nums[mid] >= target，更新 right = mid。

4. 循环结束后的处理：

   • 如果 nums[left] < target，说明目标值应该插入到 right + 1 的位置。

   • 否则，返回 right（目标值的索引）。

---

4. 示例

示例 1：

• 输入：nums = [1, 3, 5, 6]，target = 5

• 执行过程：

  1. 初始区间：left = 0，right = 3。

  2. 第一次循环：

     • mid = 1，nums[mid] = 3。

     • 3 < 5，更新 left = 2。

  3. 第二次循环：

     • mid = 2，nums[mid] = 5。

     • 5 >= 5，更新 right = 2。

  4. 循环结束，left = 2，right = 2。

  5. nums[left] = 5，返回 2。

• 输出：2

示例 2：

• 输入：nums = [1, 3, 5, 6]，target = 2

• 执行过程：

  1. 初始区间：left = 0，right = 3。

  2. 第一次循环：

     • mid = 1，nums[mid] = 3。

     • 3 >= 2，更新 right = 1。

  3. 第二次循环：

     • mid = 0，nums[mid] = 1。

     • 1 < 2，更新 left = 1。

  4. 循环结束，left = 1，right = 1。

  5. nums[left] = 3，3 > 2，返回 1。

• 输出：1

示例 3：

• 输入：nums = [1, 3, 5, 6]，target = 7

• 执行过程：

  1. 初始区间：left = 0，right = 3。

  2. 第一次循环：

     • mid = 1，nums[mid] = 3。

     • 3 < 7，更新 left = 2。

  3. 第二次循环：

     • mid = 2，nums[mid] = 5。

     • 5 < 7，更新 left = 3。

  4. 循环结束，left = 3，right = 3。

  5. nums[left] = 6，6 < 7，返回 4。

• 输出：4

四、69. x 的平方根 - 力扣（LeetCode）

方法一：暴力查找

运行代码： 

class Solution {
public:int mySqrt(int x) {// 由于两个较⼤的数相乘可能会超过 int 最⼤范围// 因此⽤ long longlong long i = 0;for (i = 0; i <= x; i++) {// 如果两个数相乘正好等于 x，直接返回 iif (i * i == x)return i;// 如果第⼀次出现两个数相乘⼤于 x，说明结果是前⼀个数if (i * i > x)return i - 1;}// 为了处理oj题需要控制所有路径都有返回值return -1;}
};

方法二：二分查找算法

运行代码：

class Solution {
public:int mySqrt(int x) {if (x < 1)return 0; // 处理边界情况int left = 1, right = x;while (left < right) {long long mid = left + (right - left + 1) / 2; // 防溢出if (mid * mid <= x)left = mid;elseright = mid - 1;}return left;}
};

1. 边界情况处理

• 如果输入的 x 小于 1，直接返回 0。因为平方根函数在 x < 1 时的整数部分为 0。

2. 二分查找

• 使用二分查找来逼近 x 的平方根。二分查找的范围是从 1 到 x，因为平方根的最大值不会超过 x。

• 初始化两个指针 left 和 right，分别指向查找范围的起始和结束位置。

3. 循环查找

• 在每次循环中，计算中间值 mid。为了防止溢出，使用 long long 类型来存储 mid，并且通过 left + (right - left + 1) / 2 的方式计算 mid，避免直接相加导致的溢出。

• 判断 mid * mid 是否小于等于 x：

  • 如果 mid * mid <= x，说明 mid 可能是平方根的候选值，或者平方根在 mid 的右侧。因此，将 left 移动到 mid。

  • 如果 mid * mid > x，说明平方根在 mid 的左侧，因此将 right 移动到 mid - 1。

4. 终止条件

• 当 left 和 right 相遇时，循环结束。此时 left 就是 x 的整数平方根。

5. 返回结果

• 最终返回 left，即 x 的整数平方根。

总结

• 该算法通过二分查找的方式高效地找到了 x 的整数平方根，时间复杂度为 O(log n)，空间复杂度为 O(1)。

• 通过使用 long long 类型和防止溢出的计算方式，确保了算法的鲁棒性。

五、852. 山脉数组的峰顶索引 - 力扣（LeetCode）

运行代码： 

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;elseright = mid - 1;}return left;}
};

1. 初始化指针

• 将 left 初始化为 1，right 初始化为 arr.size() - 2（即倒数第二个元素的索引）。

• 原因：山脉数组的峰值不可能出现在首尾（首元素没有左侧元素，尾元素没有右侧元素），因此直接排除边界。

---

2. 二分查找循环

• 循环条件：left < right，目的是让区间不断收缩，直到 left 和 right 重合。

• 中点计算：mid = left + (right - left + 1) / 2，确保中点向上取整，避免死循环。

• 比较逻辑：

  • 若 arr[mid] > arr[mid-1]，说明当前处于递增阶段，峰值在右侧（包括 mid），因此 left = mid。

  • 若 arr[mid] <= arr[mid-1]，说明处于递减阶段，峰值在左侧（不包括 mid），因此 right = mid - 1。

---

3. 返回结果

• 当 left 和 right 重合时，即为峰值的索引。

---

关键点解析

1. 排除首尾元素：直接跳过不可能为峰值的首尾元素，缩小搜索范围。

2. 向上取整的 mid：

   • 当 left 和 right 相邻时，mid 会等于 right，避免因向下取整导致的死循环。

   • 例如：left=3, right=4，若向下取整 mid=3，可能导致无限循环；向上取整则 mid=4。

3. 递增递减逻辑：

   • 通过比较 arr[mid] 和 arr[mid-1]，判断当前处于递增还是递减阶段，逐步逼近峰值。

---

示例验证

假设 arr = [1, 3, 5, 4, 2]，执行流程如下：

1. left=1, right=3（即索引范围 [1,3]）。

2. 第一次循环：

   • mid = 1 + (3-1+1)/2 = 2。

   • arr[2] = 5 > arr[1] = 3 → 递增，left=2。

3. 第二次循环：

   • mid = 2 + (3-2+1)/2 = 3。

   • arr[3] = 4 < arr[2] = 5 → 递减，right=2。

4. 循环结束，返回 left=2（正确峰值索引）。

---

复杂度

• 时间复杂度：O(log n)，二分查找每次将范围缩小一半。

• 空间复杂度：O(1)，仅需常数空间存储指针。

该算法高效且鲁棒，能够快速定位山脉数组的峰值。

六、162. 寻找峰值 - 力扣（LeetCode）

运行代码： 

class Solution {
public:int findPeakElement(vector<int>& nums) {int left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]>nums[mid-1]){left=mid;}else{right=mid-1;}}return left;}
};

1. 初始化指针

• 将 left 初始化为 0，right 初始化为 nums.size() - 1（即数组的最后一个元素的索引）。

• 原因：搜索范围覆盖整个数组。

---

2. 二分查找循环

• 循环条件：left < right，目的是让区间不断收缩，直到 left 和 right 重合。

• 中点计算：mid = left + (right - left + 1) / 2，确保中点向上取整，避免死循环。

• 比较逻辑：

  • 若 nums[mid] > nums[mid-1]，说明当前处于递增阶段，峰值在右侧（包括 mid），因此 left = mid。

  • 若 nums[mid] <= nums[mid-1]，说明处于递减阶段，峰值在左侧（不包括 mid），因此 right = mid - 1。

---

3. 返回结果

• 当 left 和 right 重合时，即为峰值元素的索引。

---

关键点解析

1. 向上取整的 mid：

   • 当 left 和 right 相邻时，mid 会等于 right，避免因向下取整导致的死循环。

   • 例如：left=3, right=4，若向下取整 mid=3，可能导致无限循环；向上取整则 mid=4。

2. 递增递减逻辑：

   • 通过比较 nums[mid] 和 nums[mid-1]，判断当前处于递增还是递减阶段，逐步逼近峰值。

3. 边界处理：

   • 如果数组只有一个元素，直接返回 0。

   • 如果数组是严格递增的，返回最后一个元素的索引。

   • 如果数组是严格递减的，返回第一个元素的索引。

---

示例验证

假设 nums = [1, 2, 3, 1]，执行流程如下：

1. left=0, right=3（即索引范围 [0,3]）。

2. 第一次循环：

   • mid = 0 + (3-0+1)/2 = 2。

   • nums[2] = 3 > nums[1] = 2 → 递增，left=2。

3. 第二次循环：

   • mid = 2 + (3-2+1)/2 = 3。

   • nums[3] = 1 < nums[2] = 3 → 递减，right=2。

4. 循环结束，返回 left=2（正确峰值索引）。

---

复杂度

• 时间复杂度：O(log n)，二分查找每次将范围缩小一半。

• 空间复杂度：O(1)，仅需常数空间存储指针。

该算法高效且鲁棒，能够快速定位数组中的一个峰值元素。

七、153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

 运行代码：

class Solution {
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1;int x = nums[right]; // 标记⼀下最后⼀个位置的值while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] > x)left = mid + 1;elseright = mid;}return nums[left];}
};

1. 初始化指针

• 将 left 初始化为 0，right 初始化为 nums.size() - 1（即数组的最后一个元素的索引）。

• x 的作用：x 是数组最后一个元素的值，用于判断当前区间是否包含旋转点（即最小值所在的区间）。

---

2. 二分查找循环

• 循环条件：left < right，目的是让区间不断收缩，直到 left 和 right 重合。

• 中点计算：mid = left + (right - left) / 2，确保中点向下取整。

• 比较逻辑：

  • 若 nums[mid] > x，说明 mid 处于旋转点的左侧（较大的部分），最小值在右侧，因此 left = mid + 1。

  • 若 nums[mid] <= x，说明 mid 处于旋转点的右侧（较小的部分），最小值在左侧（包括 mid），因此 right = mid。

---

3. 返回结果

• 当 left 和 right 重合时，nums[left] 即为数组的最小值。

---

关键点解析

1. 旋转排序数组的特性：

   • 旋转排序数组可以被分为两个部分：左侧是较大的部分，右侧是较小的部分。

   • 最小值是这两个部分的分界点。

2. x 的作用：

   • x 是数组最后一个元素的值，用于判断当前区间是否包含旋转点。

   • 如果 nums[mid] > x，说明 mid 处于较大的部分，最小值在右侧。

   • 如果 nums[mid] <= x，说明 mid 处于较小的部分，最小值在左侧。

3. 二分查找的调整：

   • 通过比较 nums[mid] 和 x，逐步缩小搜索范围，最终找到最小值。

---

示例验证

假设 nums = [4,5,6,7,0,1,2]，执行流程如下：

1. left=0, right=6，x=2（最后一个元素的值）。

2. 第一次循环：

   • mid = 0 + (6-0)/2 = 3。

   • nums[3] = 7 > x = 2 → 处于较大的部分，最小值在右侧，left=4。

3. 第二次循环：

   • mid = 4 + (6-4)/2 = 5。

   • nums[5] = 1 <= x = 2 → 处于较小的部分，最小值在左侧（包括 mid），right=5。

4. 第三次循环：

   • mid = 4 + (5-4)/2 = 4。

   • nums[4] = 0 <= x = 2 → 处于较小的部分，最小值在左侧（包括 mid），right=4。

5. 循环结束，返回 nums[4] = 0（正确的最小值）。

---

复杂度

• 时间复杂度：O(log n)，二分查找每次将范围缩小一半。

• 空间复杂度：O(1)，仅需常数空间存储指针。

该算法高效且鲁棒，能够快速定位旋转排序数组中的最小值。

八、LCR 173. 点名 - 力扣（LeetCode）

运行代码： 

class Solution {
public:int takeAttendance(vector<int>& records) {int left=0,right=records.size()-1;while(left<right){int mid=left+(right-left)/2;if(records[mid]==mid){left=mid+1;}else{right=mid;}}return left == records[left] ? left + 1 : left;}
};

1. 初始化指针

• 将 left 初始化为 0，right 初始化为数组的最后一个元素的索引。

• 原因：假设数组原本是严格递增的，且缺失的元素可能在数组范围内或范围外（如数组完整时返回长度）。

---

2. 二分查找循环

• 循环条件：left < right，目的是让区间不断收缩，直到 left 和 right 重合。

• 中点计算：mid 向下取整，避免死循环。

• 比较逻辑：

  • 若 records[mid] == mid，说明左侧（包括 mid）的元素与下标匹配，缺失在右侧，因此 left = mid + 1。

  • 若 records[mid] != mid，说明缺失发生在左侧或当前点，因此 right = mid。

---

3. 返回结果

• 当 left 和 right 重合时：

  • 若 records[left] == left，说明数组是完整的，返回 left + 1（即数组长度）。

  • 若 records[left] != left，说明 left 是缺失的元素。

---

关键点解析

1. 严格递增的特性：

   • 若数组完整，元素值应与下标完全匹配（records[i] = i）。

   • 若存在缺失元素，第一个不满足 records[i] = i 的位置即为缺失值。

2. 二分查找的调整：

   • 通过比较 records[mid] 和 mid，逐步缩小范围，最终定位到缺失的位置。

3. 边界处理：

   • 如果数组完整（如 [0,1,2,3]），返回 left + 1（即 4）。

   • 如果缺失在数组范围内（如 [0,1,3,4]），返回 left（即 2）。

---

示例验证

1. 示例 1：records = [0,1,3,4]

   • 初始 left=0, right=3。

   • 第一次循环：

     • mid=1, records[1]=1 == 1 → left=2。

   • 第二次循环：

     • mid=2, records[2]=3 != 2 → right=2。

   • 循环结束，返回 left=2（正确缺失值）。

2. 示例 2：records = [0,1,2,3]

   • 初始 left=0, right=3。

   • 循环过程：

     • mid=1, records[1]=1 → left=2。

     • mid=2, records[2]=2 → left=3。

   • 循环结束，records[3]=3，返回 3 + 1 = 4（数组长度）。

---

复杂度

• 时间复杂度：O(log n)，二分查找每次将范围缩小一半。

• 空间复杂度：O(1)，仅需常数空间存储指针。

该算法高效且鲁棒，能快速定位严格递增数组中的缺失元素。