20. 二分查找-贪心问题

正文

“二分搜索 + 贪心算法”是一种极高频的进阶算法组合。它通常用于解决“最大化最小值”或“最小化最大值”的问题。这种问题的特点是直接计算很难，但“给定一个答案，验证其是否可行”却非常简单。

算法模板

fun solve(nums: IntArray, k: Int): Int {
    // 1. 确定搜索范围 [left, right]
    var left = 1 // 最小值（根据题意调整）
    var right = nums.sum() // 最大值（根据题意调整）
    var ans = 0

    while (left <= right) {
        val mid = left + (right - left) / 2
        
        // 2. 贪心验证：如果以 mid 为标准是可行的
        if (check(nums, k, mid)) {
            // 如果 mid 可行，尝试寻找更优解
            ans = mid
            // 若求最大化最小值，向右收缩：left = mid + 1
            // 若求最小化最大值，向左收缩：right = mid - 1
            left = mid + 1 
        } else {
            // 如果 mid 不行，调整范围
            right = mid - 1
        }
    }
    return ans
}

// 贪心验证函数：检查 mid 是否满足题目要求
private fun check(nums: IntArray, k: Int, mid: Int): Boolean {
    var count = 0
    // 实现具体的贪心逻辑...
    return count >= k
}

使用说明

1. 核心思想：
   将搜索对象从“索引”转变为“答案”。我们在答案的可能范围内进行二分，利用贪心策略验证每一个猜测。

2. 适用场景：

   • 最大化最小值：如“分割数组的最大值”、“木棍切割问题”、“安排牛舍”。
   • 最小化最大值：如“完成任务的最少时间”。

3. 核心步骤：

   • Step 1：明确答案的取值范围（left 和 right）。
   • Step 2：编写 check 函数，通常使用贪心策略在 $O(N)$ 时间内完成验证。
   • Step 3：根据 check 的结果和求最值的类型（最大/最小），决定指针移动方向。

4. 注意点：

   • 确保搜索空间是单调的。
   • check 函数的逻辑直接决定了算法的正确性。
   • 对于大数求和，注意 right 的溢出问题（必要时改用 Long）。