每日算法-250414

每日算法学习记录 - 240414

记录今天学习和解决的两道 LeetCode 算法题，主要涉及二分查找的应用。

162. 寻找峰值

题目描述

思路分析

核心思想：二分查找

题目要求找到数组中的任意一个峰值。峰值定义为比其相邻元素都大的元素。题目还隐含了一个条件：数组边界之外视为负无穷 (-∞)。这保证了数组中至少存在一个峰值。
由于题目要求的时间复杂度为 $O(\log n)$，并且数组具有可以通过比较中间元素与其邻居来缩小范围的特性，自然想到使用二分查找。

解题过程

我们可以利用二分查找来不断缩小可能包含峰值的范围。设查找区间为 [left, right]。

1. 取中间索引 mid = left + (right - left) / 2。

2. 比较 nums[mid] 和它的右邻居 nums[mid + 1]：

   • 如果 nums[mid] > nums[mid + 1]：这意味着我们正处于一个下降的坡段，或者 mid 本身就是一个峰值（因为它的右边更小）。无论是哪种情况，mid 左侧（包括 mid）必定存在一个峰值。因此，我们可以安全地舍弃右半部分，将搜索范围缩小为 [left, mid]。在代码实现中，通过 right = mid - 1 来配合 while (left <= right) 和最后返回 left 的模板，确保找到峰值。
   • 如果 nums[mid] <= nums[mid + 1]：这意味着我们正处于一个上升的坡段。那么 mid 右侧必定存在一个峰值（因为数组末尾是负无穷，所以上升趋势最终必然会下降）。因此，我们可以安全地舍弃左半部分（包括 mid），将搜索范围缩小为 [mid + 1, right]。代码实现为 left = mid + 1。

3. 边界处理：需要特别注意 mid + 1 是否越界。当 mid 是数组最后一个元素的索引 (nums.length - 1) 时，它天然满足峰值条件（右侧负无穷）。我们的比较逻辑 if (mid == nums.length - 1 || nums[mid] > nums[mid + 1]) 通过短路或 || 优雅地处理了这个边界情况：如果 mid 是最后一个元素，mid == nums.length - 1 为真，条件直接满足，执行 right = mid - 1，不会访问 nums[mid + 1]。

4. 循环终止：当 left > right 时，循环终止。根据我们使用的二分查找模板，此时 left 指向的位置即为一个峰值元素。

复杂度分析

• 时间复杂度: $O(\log n)$，其中 $n$ 是数组 nums 的长度。每次迭代，查找范围都减半。
• 空间复杂度: $O(1)$，只使用了常数级别的额外空间。

代码实现

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

---

278. 第一个错误的版本

题目描述

思路分析

核心思想：二分查找

题目指出，一旦一个版本是错误的，其后续所有版本也都是错误的。这表明版本号序列具有单调性：从某个版本开始（第一个错误版本），isBadVersion() 的返回值从 false 变为 true，并且之后一直保持 true。即 false, false, ..., false, true, true, ... 的模式。
这种明确的二段性是使用二分查找来寻找第一个 true（即第一个错误版本）的理想场景。

解题过程

我们的目标是找到满足 isBadVersion(version) 为 true 的最小版本号 version。

1. 初始化查找区间 [left, right] 为 [1, n]。
2. 取中间版本号 mid = left + (right - left) / 2。
3. 调用 isBadVersion(mid) 检查中间版本：
   • 如果 isBadVersion(mid) 返回 true：说明 mid 版本是错误的。但它不一定是 第一个 错误的版本，第一个错误的版本可能在 mid 或 mid 之前。因此，我们需要在左半部分（包括 mid）继续查找，将搜索范围缩小为 [left, mid - 1]（根据代码模板）。
   • 如果 isBadVersion(mid) 返回 false：说明 mid 版本是正确的。那么第一个错误的版本必定在 mid 之后。因此，我们需要在右半部分查找，将搜索范围缩小为 [mid + 1, right]。
4. 循环终止：当 left > right 时，循环终止。根据我们使用的二分查找模板（寻找下界/第一个满足条件的位置），此时 left 指向的就是第一个错误的版本号。

复杂度分析

• 时间复杂度: $O(\log n)$，其中 $n$ 是版本总数。每次调用 isBadVersion，查找范围都减半。
• 空间复杂度: $O(1)$，只使用了常数级别的额外空间。

代码实现

/* The isBadVersion API is defined in the parent class VersionControl.boolean isBadVersion(int version); */public class Solution extends VersionControl {public int firstBadVersion(int n) {int left = 1, right = n;while (left <= right) {int mid = left + (right - left) / 2;if (isBadVersion(mid)) {right = mid - 1;} else {left = mid + 1;}}return left;}
}