二分的本质是定义并找到某种性质的边界，边界的一侧满足该性质，另一侧不满足该性质。

  • 对一个区间按某种性质进行二分时，利用该性质的判断条件，每一轮都能将区间范围减半，范围减半后的区间进入下一轮二分。显然，每次进行二分的区间都包含要求的答案，这意味着若区间长度变为 1 时，区间里的那个数就是答案。
  • 使用二分法一定能找出边界，但找出的边界可能不满足算法题对解的定义，所以二分算法题可能没有解。

定义某种性质的边界的示例：

  1. 找出升序数组中某个元素的起始位置和终止位置：

    • 起始位置：最左边的大于等于该元素的数的下标；
    • 终止位置：最右边的小于等于该元素的数的下标。
    元素索引    0 1 2 3 4 5
数组元素    1 2 2 3 3 4
目标元素          3
索引区间          [3,4]

整数二分

整数二分的要点在于中点的选取，有两个模板：

  1. l = mid，r 不变，即二分后的区间是 [mid, r] 或 [l, mid-1]，此时取 mid = (l+r+1)/2；
    • 求 mid 时有个加 1，若没有加 1，当 r == l+1 时，mid=(l+l+1)/2 下取整的结果就是 l，新区间 [mid, r] 依然是 [l, r]，和二分之前的区间完全相同，造成死循环。
  2. r = mid，l 不变，即二分后的区间是 [l, mid] 或 [mid+1, r]，此时取 mid = (l+r)/2。
  • 模板记法：二分后新区间的 -1 和 mid 的 +1 同时出现。

找出升序数组中某个元素的起始位置和终止位置：

func main() {
    var n, q, k int
    fmt.Scanf("%d %d", &n, &q)
    nums := make([]int, n)
    for i := range nums {
        fmt.Scanf("%d", &nums[i])
    }
    
    for q > 0 { // q 个询问
        fmt.Scanf("%d", &k)
        q--
    
        l, r := 0, len(nums)-1
        for l < r {
            mid := (l+r)/2
            // 1. 找最左边的 >= k 的数的下标
            if nums[mid] >= k {
                r = mid     // l 不变
            } else {
                l = mid+1   // r 不变
            }
        }
        if nums[l] != k {
            fmt.Println("-1 -1")
            continue
        }
        
        fmt.Printf("%d ", l)
        
        l, r = 0, len(nums)-1
        for l < r {
            mid := (l+r+1)/2
            // 2. 找最右边的 <= k 的数的下标
            if nums[mid] <= k {
                l = mid     // r 不变
            } else {
                r = mid-1   // l 不变
            }
        }
        fmt.Printf("%d\n", l)
    }
}

浮点数二分

浮点数的三次方根：

func main() {
    var n float64
    fmt.Scanf("%f", &n)
    l, r := -10000.0, 10000.0 // −10000≤n≤10000
    for r-l > 1e-8 { // 经验值：比精度多 2 位
        mid := (l+r)/2
        if mid*mid*mid > n {
            r = mid 
        } else {
            l = mid
        }
    }
    fmt.Printf("%.6f\n", l)
}

References