当前位置：首页 > article >正文

2、二分和贪心

article 2025/4/1 3:42:51

一、二分

这里有个小技巧，你会发现，只要是求最大最小最多等等的贪心过程，我们就有3种方法：①二分②贪心算法③动态规划
我们先讲二分和贪心，动态规划比较麻烦，留到后期。

1、了解

在这里插入图片描述

2、模版

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 二分查找的前提是数组必须是有序的
        int left = 0;                  // 左边界，初始为数组起始位置
        int right = nums.size() - 1;   // 右边界，初始为数组末尾位置

        // 当左边界小于等于右边界时，继续查找
        while (left <= right) {
            int mid = left + (right - left) / 2; // 计算中间位置，避免溢出

            if (nums[mid] == target) {
                // 如果中间值等于目标值，直接返回中间位置
                return mid;
            } else if (nums[mid] < target) {
                // 如果中间值小于目标值，说明目标值在右半部分
                left = mid + 1; // 移动左边界
            } else {
                // 如果中间值大于目标值，说明目标值在左半部分
                right = mid - 1; // 移动右边界
            }
        }

        // 如果未找到目标值，返回 -1
        return -1;
    }
};

以下是提供的C++二分查找代码的分析和说明：

代码分析

这段代码实现了标准的二分查找算法，结构清晰且符合最佳实践。关键点如下：

有序数组处理：
- 明确说明输入数组必须有序（符合二分查找的前提条件）。
边界初始化：
```
int left = 0;
int right = nums.size() - 1;
```
- 初始化左右指针为数组的起始和末尾位置，逻辑正确。
循环条件：
```
while (left <= right)
```
- 使用 <= 确保区间内仅剩一个元素时仍能进入循环，避免漏查。
中间值计算：
```
int mid = left + (right - left) / 2;
```
- 避免 (left + right) 的潜在溢出问题，更安全的写法。
条件分支：
- 找到目标值时直接返回索引。
- 未找到时调整左右边界，逐步缩小搜索范围，逻辑正确。

测试用例验证

示例 1：目标存在

输入：nums = [-1, 0, 3, 5, 9, 12], target = 9
执行流程：
1. left=0, right=5 → mid=2（值为3）→ 3 < 9 → left=3
2. left=3, right=5 → mid=4（值为9）→ 命中，返回4。
输出：4（正确）

示例 2：目标不存在

输入：nums = [-1, 0, 3, 5, 9, 12], target = 2
执行流程：
1. mid依次计算为2、0、1 → 最终 left > right，退出循环。
输出：-1（正确）

边界情况测试

空数组：
```
vector<int> nums = {};
int target = 5;
```
- 直接返回 -1，正确处理。

单元素数组：

vector<int> nums = {5};
int target = 5;  // 返回0
int target = 2;  // 返回-1

结果符合预期。

目标在两端：

vector<int> nums = [2, 4, 6];
int target = 2;  // 返回0
int target = 6;  // 返回2

均正确命中。

总结

代码完全正确，涵盖了二分查找的核心逻辑，且处理了所有边界情况。适用于有序数组的快速查找，时间复杂度为 O(log n)，空间复杂度为 O(1)。

3、例题

ACwing分巧克力
- 这道题的思路：
  - 假设需要的大小是 1-N中的某一个数，这里的N就是 n的数据范围最大值。我从这个数里找中间值，作为所有巧克力的边长，看满足这个边长的情况下，我能拿到多少块巧克力。
  - 如果拿到的巧克力的数量小于小朋友人数，说明我们需要扩大巧克力数量，就要缩减边长的长度，移动 r = mid-1 。反之，大于就移动 l =mid+1 。
  - 最终结果就是 l -1 。之所以 l要减一，是因为我上面的式子是 l=mid+1 ，但实际上答案是 mid 。所以我们l要减一。

二、贪心

1、了解

举例了解：如果你需要从一个数组中，找到2个数之和是最大的，那么我们就找最大的数，就行了。
- 也就是说，我们需要什么最大，就找什么的最大值。
贪心是一种思想，而不是一个模版之类的题。其实在算法中，模版只是其次，你要的是做题思想，这个需要做题提升。

2、例题

ACwing1522排成最小的数字
首先要知道什么是前导0和后导0
- 前导零
  - 定义：出现在字符串或数字最左侧的无效零。
  - 示例：
    - 数字 00123 的前导零是开头的两个 0，有效部分是 123。
- 后导0
  - 定义：出现在字符串或数字最右侧的无效零。
  - 示例：
    - 数字 0012300 的后导零是尾部的两个 0，有效部分是 00123。
- 题解过程：
  - 我们要先排序，再处理前导0 。为什么呢？
    - 因为：当我给你 0-010-0234的3个数字时。假设排序后是00100234，那么我们只删除前2个0，最终为100234。如果先删，就可能出现，你不知道删哪一个，或者你删成每个数字的第一个0.就会导致错误。
  - 因为这个排序具有反对称性、传递性、完整性。用 return a + b < b + a; 的方法排序。