论二分✨（慎入）

@llx

2025-06-20 21:19:38

发布于：浙江

14阅读

0回复

0点赞

注：今天的内容稍稍有点水，不喜勿喷
一、二分查找（Binary Search）

原理说明

二分查找基于有序集合的减治策略，通过每次将搜索范围减半实现O(log n)时间复杂度。算法核心是维护查找区间[l, r]，通过中间值mid与目标值的比较决定搜索方向。

经典案例：有序数组查找

int BinarySearch(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;  // 防溢出写法
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

应用场景：
数据库索引、游戏分数排行榜、词典查询等有序数据检索。

二、二分答案（Binary Search on Answer）

原理说明
当问题满足<单调性>条件时，通过二分枚举可能的解，用验证函数判断解的有效性。适用于"求最大最小值"或"最小最大值"类问题。
典型案例：木材切割

bool isValid(vector<int>& woods, int k, int cut) {
    int sum = 0;
    for (int wood : woods) 
        sum += wood / cut;
    return sum >= k;
}

int maxCutLength(vector<int>& woods, int k) {
    int l = 1, r = *max_element(woods.begin(), woods.end());
    while (l < r) {
        int mid = l + (r - l + 1) / 2;  // 向上取整
        if (isValid(woods, k, mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}