本质

找到某种性质将区间一份为二，一半满足，一半不满足。每次选择答案所在的区间
二分查找

模版一：寻找绿色区间的左端点

若绿色区间满足的性质为：大于等于target，则寻找到的结果为大于等于target最小的数。

1
2
3
4
5
6
7
8
9
10
11
func binarySearch(l, r int) int{
	for l < r {
    	mid := l + (r - l)/2
        if check(mid){
        	r = mid
        }else {
        	l = mid + 1
        }
    }
    return l
}

模版二：寻找红色区间的右端点

若红色区间满足的性质为：小于等于target，则寻找到的结果为小于等于target最大的数。

1
2
3
4
5
6
7
8
9
10
11
func binarySearch(l, r int) int{
	for l < r {
    	mid := l + (r - l + 1)/2 //由于下取整的原因需要+1
        if check(mid){
        	l = mid
        }else {
        	r = mid - 1
        }
    }
    return l
}