1
"最大化最小值"场景（check 单调递减）：
2
  x 越小 → 越容易满足 → check(x) 越可能是 true
3
  x 越大 → 越难满足   → check(x) 越可能是 false
4

5
  check(x): T T T T T F F F F
6
            ↑        ↑
7
         小答案    大答案
8
                        ↑ 最后一个 T = 最大可行解
9

10
"最小化最大值"场景（check 单调递增）：
11
  x 越小 → 越难满足   → check(x) 越可能是 false
12
  x 越大 → 越容易满足 → check(x) 越可能是 true
13

14
  check(x): F F F T T T T T
15
                   ↑
16
              第一个 T = 最小可行解

1
二分答案的通用步骤：
2
┌──────────────────────────────────────────────────────┐
3
│ 1. 确定答案范围 [lo, hi]                               │
4
│    - lo = 可能的最小答案                                │
5
│    - hi = 可能的最大答案（可以设一个安全的上界）            │
6
│                                                      │
7
│ 2. 设计 check(mid) 函数                               │
8
│    - 输入：候选答案 mid                                 │
9
│    - 输出：按照这个"答案"，能否满足题目要求？               │
10
│    - 这通常是个贪心模拟——check 才是题目真正的核心          │
11
│                                                      │
12
│ 3. 二分搜索                                            │
13
│    - 如果 check(mid) 可行 → 尝试更大的（或更小的）         │
14
│    - 如果 check(mid) 不可行 → 调整范围                   │
15
│    - 循环结束时 lo-1（或 hi）即为答案                     │
16
│                                                      │
17
│ 4. 验证边界                                            │
18
│    - 检查 lo=0 或 hi=1e9 等极端情况                      │
19
└──────────────────────────────────────────────────────┘

1
// 统一模板：在 [lo, hi) 左闭右开区间内查找
2
// 返回第一个 >= target 的位置（即 std::lower_bound）
3
//
4
// 核心原则：
5
// - 区间 [lo, hi) 始终包含答案
6
// - 每次迭代缩小一半
7
// - 循环条件 lo < hi（区间非空）
8
int lower_bound(const std::vector<int>& arr, int target) {
9
    int lo = 0, hi = arr.size();  // [lo, hi)
10

11
    while (lo < hi) {
12
        int mid = lo + (hi - lo) / 2;  // 防止溢出
13
        if (arr[mid] < target) {
14
            lo = mid + 1;  // 答案在右半边
15
        } else {
16
            hi = mid;      // arr[mid] >= target，mid 可能是答案
17
        }
18
    }
19
    return lo;  // lo == hi，是第一个 >= target 的位置
20
}
21

22
// upper_bound：返回第一个 > target 的位置
23
int upper_bound(const std::vector<int>& arr, int target) {
24
    int lo = 0, hi = arr.size();
25
    while (lo < hi) {
26
        int mid = lo + (hi - lo) / 2;
27
        if (arr[mid] <= target) {
28
            lo = mid + 1;
29
        } else {
30
            hi = mid;
31
        }
32
    }
33
    return lo;
34
}

1
// LeetCode 33: 搜索旋转排序数组
2
// 输入: [4,5,6,7,0,1,2], target=0 → 输出: 4
3
//
4
// 核心洞察：mid 一定会把数组分成两半，其中至少一半是有序的
5
int searchRotated(const std::vector<int>& nums, int target) {
6
    int lo = 0, hi = nums.size() - 1;
7

8
    while (lo <= hi) {
9
        int mid = lo + (hi - lo) / 2;
10

11
        if (nums[mid] == target) return mid;
12

13
        // 判断哪一半是有序的
14
        if (nums[lo] <= nums[mid]) {
15
            // 左半有序
16
            if (nums[lo] <= target && target < nums[mid]) {
17
                hi = mid - 1;  // target 在左半
18
            } else {
19
                lo = mid + 1;  // target 在右半
20
            }
21
        } else {
22
            // 右半有序
23
            if (nums[mid] < target && target <= nums[hi]) {
24
                lo = mid + 1;  // target 在右半
25
            } else {
26
                hi = mid - 1;  // target 在左半
27
            }
28
        }
29
    }
30
    return -1;
31
}

1
// LeetCode 81: 搜索旋转排序数组 II（含重复元素）
2
// 当 nums[lo] == nums[mid] == nums[hi] 时，无法判断哪边有序
3
bool searchRotatedDup(const std::vector<int>& nums, int target) {
4
    int lo = 0, hi = nums.size() - 1;
5

6
    while (lo <= hi) {
7
        int mid = lo + (hi - lo) / 2;
8

9
        if (nums[mid] == target) return true;
10

11
        // 致命情况：无法判断哪边有序
12
        if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
13
            ++lo;
14
            --hi;
15
            continue;
16
        }
17

18
        if (nums[lo] <= nums[mid]) {
19
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
20
            else                                          lo = mid + 1;
21
        } else {
22
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
23
            else                                          hi = mid - 1;
24
        }
25
    }
26
    return false;
27
}

1
// LeetCode 153: 寻找旋转排序数组中的最小值（无重复）
2
// 核心：最小值就是"旋转点"
3
int findMin(const std::vector<int>& nums) {
4
    int lo = 0, hi = nums.size() - 1;
5

6
    while (lo < hi) {
7
        int mid = lo + (hi - lo) / 2;
8

9
        // 与 nums[hi] 比较（不是 nums[lo]！）
10
        if (nums[mid] > nums[hi]) {
11
            lo = mid + 1;  // 最小值一定在右半
12
        } else {
13
            hi = mid;      // nums[mid] <= nums[hi]，mid 可能是最小值
14
        }
15
    }
16
    return nums[lo];
17
}

1
// 与"分割数组的最大值"几乎一样——同一套模板
2
int shipWithinDays(std::vector<int>& weights, int days) {
3
    int lo = *std::max_element(weights.begin(), weights.end());
4
    int hi = std::accumulate(weights.begin(), weights.end(), 0);
5

6
    while (lo < hi) {
7
        int mid = lo + (hi - lo) / 2;
8

9
        int needDays = 1;
10
        int currentLoad = 0;
11
        for (int w : weights) {
12
            if (currentLoad + w > mid) {
13
                ++needDays;
14
                currentLoad = w;
15
            } else {
16
                currentLoad += w;
17
            }
18
        }
19

20
        if (needDays <= days) hi = mid;
21
        else                  lo = mid + 1;
22
    }
23
    return lo;
24
}

1
// 关键洞察：如果 nums[mid] < nums[mid+1]，则右侧一定存在峰值
2
// 因为 nums[n] = -∞，"上升"最终一定会转为"下降"
3
int findPeakElement(const std::vector<int>& nums) {
4
    int lo = 0, hi = nums.size() - 1;
5

6
    while (lo < hi) {
7
        int mid = lo + (hi - lo) / 2;
8

9
        if (nums[mid] < nums[mid + 1]) {
10
            lo = mid + 1;  // 右侧在上升，峰值在右边
11
        } else {
12
            hi = mid;      // mid 可能本身就是峰值，或在左边
13
        }
14
    }
15
    return lo;
16
}

1
// 二分答案 + 滑动窗口 check
2
// check(dist): 距离 <= dist 的数对数量是否 >= k？
3
int smallestDistancePair(std::vector<int>& nums, int k) {
4
    std::sort(nums.begin(), nums.end());
5
    int n = nums.size();
6

7
    int lo = 0;
8
    int hi = nums.back() - nums.front();
9

10
    while (lo < hi) {
11
        int mid = lo + (hi - lo) / 2;
12

13
        // 滑动窗口统计 <= mid 的数对数量
14
        int count = 0;
15
        int left = 0;
16
        for (int right = 0; right < n; ++right) {
17
            while (nums[right] - nums[left] > mid) {
18
                ++left;
19
            }
20
            count += right - left;  // [left, right) 内的都对
21
        }
22

23
        if (count >= k) {
24
            hi = mid;
25
        } else {
26
            lo = mid + 1;
27
        }
28
    }
29
    return lo;
30
}

1
// 场景：设计一个 Boss 关卡，Boss 有 HP 值
2
// 已知玩家的 DPS 曲线（随战斗时间递减，模拟疲劳）
3
// 需要找一个 HP 值，使得玩家恰好能在 120 秒内击败 Boss
4
// → 二分答案：猜 HP，模拟战斗验证
5

6
struct Player {
7
    float baseDps;        // 基础 DPS
8
    float fatigueRate;    // 疲劳速率（每秒 DPS 衰减百分比）
9
};
10

11
// check(bossHp): 给定 Boss 血量，玩家能否在 120 秒内击杀？
12
bool canKillBoss(float bossHp, const Player& player, float timeLimit) {
13
    float remainingHp = bossHp;
14
    float currentDps = player.baseDps;
15

16
    // 以 0.1 秒为步长模拟战斗
17
    for (float t = 0; t < timeLimit; t += 0.1f) {
18
        float damage = currentDps * 0.1f;         // 0.1 秒的伤害
19
        remainingHp -= damage;
20

21
        if (remainingHp <= 0) return true;         // 击杀了
22

23
        // DPS 随疲劳衰减
24
        currentDps *= (1.0f - player.fatigueRate * 0.1f);
25
        if (currentDps < player.baseDps * 0.3f) {  // 最低 DPS 保底
26
            currentDps = player.baseDps * 0.3f;
27
        }
28
    }
29
    return remainingHp <= 0;
30
}
31

32
// 二分答案找最优 Boss 血量
33
float findOptimalBossHp(const Player& player, float timeLimit) {
34
    float lo = 100.0f;     // 最低血量（太简单）
35
    float hi = 100000.0f;  // 最高血量（太难）
36

37
    for (int iter = 0; iter < 60; ++iter) {
38
        float mid = (lo + hi) / 2.0f;
39
        if (canKillBoss(mid, player, timeLimit)) {
40
            lo = mid;  // 能击杀 → 尝试更高血量
41
        } else {
42
            hi = mid;  // 不能 → 降低血量
43
        }
44
    }
45
    return lo;  // 玩家恰好能击败的最大血量
46
}

1
struct LODMetrics {
2
    int   triangleCount;  // 该 LOD 级别的三角面数
3
    float visualScore;    // 画质评分 (0-1)
4
};
5

6
// 检查某组 LOD 距离阈值是否满足性能预算
7
// distances[i] = 第 i 个 LOD 级别的切换距离
8
bool checkLODBudget(const std::vector<float>& distances,
9
                    const std::vector<LODMetrics>& lods,
10
                    int maxTriangles) {
11
    // 简化模拟：在典型视角下，估算可见三角面总数
12
    // 实际项目中会用 GPU Profiler 或更复杂的视锥采样
13
    float typicalViewDist = 500.0f;
14
    float totalTriangles = 0;
15

16
    for (size_t i = 0; i < lods.size(); ++i) {
17
        float effectiveDist = (i + 1 < distances.size())
18
                            ? std::min(distances[i + 1], typicalViewDist)
19
                            : typicalViewDist;
20

21
        if (effectiveDist > distances[i]) {
22
            float weight = (effectiveDist - distances[i]) / typicalViewDist;
23
            totalTriangles += lods[i].triangleCount * weight;
24
        }
25
    }
26

27
    return totalTriangles <= maxTriangles;
28
}
29

30
// 二分搜索最高 LOD 的"最远距离"（保证性能不超标）
31
float findMaxLODDistance(const std::vector<LODMetrics>& lods, int maxTriangles) {
32
    float lo = 50.0f;    // 至少能显示 50 米
33
    float hi = 1000.0f;  // 最多 1000 米
34

35
    for (int iter = 0; iter < 50; ++iter) {
36
        float mid = (lo + hi) / 2.0f;
37

38
        // 构造当前的 LOD 距离配置
39
        std::vector<float> distances = {0, mid, mid * 2.5f, mid * 5.0f};
40

41
        if (checkLODBudget(distances, lods, maxTriangles)) {
42
            lo = mid;  // 性能允许 → 尝试更远
43
        } else {
44
            hi = mid;  // 性能超标 → 降低距离
45
        }
46
    }
47
    return lo;
48
}

1
struct Asset {
2
    std::string name;
3
    int         sizeMB;
4
    int         priority;  // 1=必须, 2=重要, 3=可选
5
};
6

7
// check(maxSize): 只加载总大小 <= maxSize 的资源，能否满足必须资源？
8
bool canLoadWithinBudget(const std::vector<Asset>& assets,
9
                          int maxSize, int& loadedCount) {
10
    int currentSize = 0;
11
    loadedCount = 0;
12

13
    // 按优先级贪心加载
14
    for (const auto& asset : assets) {
15
        if (currentSize + asset.sizeMB <= maxSize) {
16
            currentSize += asset.sizeMB;
17
            ++loadedCount;
18
        } else if (asset.priority == 1) {
19
            return false;  // 必须资源没加载上
20
        }
21
    }
22
    return true;
23
}
24

25
int findMaxResourceBudget(const std::vector<Asset>& assets) {
26
    // 预排序：优先级高的在前
27
    auto sorted = assets;
28
    std::sort(sorted.begin(), sorted.end(),
29
        [](const Asset& a, const Asset& b) {
30
            return a.priority < b.priority;
31
        });
32

33
    int totalSize = 0;
34
    for (const auto& a : sorted) totalSize += a.sizeMB;
35

36
    int lo = 0, hi = totalSize;
37
    int loadedCount = 0;
38

39
    while (lo < hi) {
40
        int mid = lo + (hi - lo + 1) / 2;  // 最大化 → 向上取整
41
        int count = 0;
42

43
        if (canLoadWithinBudget(sorted, mid, count)) {
44
            lo = mid;
45
            loadedCount = count;
46
        } else {
47
            hi = mid - 1;
48
        }
49
    }
50
    return lo;
51
}