二分答案

查找与遍历

说明

对单调可行性条件二分最小解；需要先证明可行性随答案单调。

分析

有些问题不直接给出有序数组，但“答案达到某值后始终可行”形成了单调序列。feasible(mid) 将候选答案转成布尔判断，二分寻找第一个 true。

图解推演

正文在非负整数 0..20 寻找 n²≥30 的最小 n。依次试 10（可行）、5（不可行）、8（可行）、7（可行）、6（可行），最终收敛到 6。可行性只在这个非负区间单调；若包含负数，平方先减后增，就不能直接用这一谓词二分。

查看图表代码

适用前提与边界

使用前要证明边界覆盖解，并防止不可行时把 hi 误当作有效答案。

示例输入与调用

fmt.Println(FirstFeasible(0, 20, func(n int) bool { return n*n >= 30 }))

运行输出

6

完整 Go 示例

package main

import "fmt"

func FirstFeasible(lo, hi int, feasible func(int) bool) int {
	for lo < hi {
		mid := lo + (hi-lo)/2
		if feasible(mid) {
			hi = mid
		} else {
			lo = mid + 1
		}
	}
	return lo
}

func main() {
	fmt.Println(FirstFeasible(0, 20, func(n int) bool { return n*n >= 30 }))
}