第 14 讲：二分查找与二分答案

// 返回 x 的下标；不存在返回 -1
func BinarySearch(a []int, x int) int {
    lo, hi := 0, len(a)-1 // 闭区间：hi 是合法下标
    for lo <= hi {        // 区间非空的条件是 lo <= hi
        mid := lo + (hi-lo)/2 // ⚠️ 不写 (lo+hi)/2，防溢出
        switch {
        case a[mid] == x:
            return mid
        case a[mid] < x:
            lo = mid + 1 // mid 已排除，收缩到 [mid+1, hi]
        default:
            hi = mid - 1 // mid 已排除，收缩到 [lo, mid-1]
        }
    }
    return -1
}

mid := (lo + hi) / 2   // ✗  lo+hi 可能溢出
mid := lo + (hi-lo)/2  // ✓  差值不会溢出

for lo < hi {
    mid := lo + (hi-lo)/2
    if a[mid] < x {
        lo = mid + 1
    } else {
        lo = mid   // ✗ 当 hi == lo+1 时 mid == lo，区间不缩小 ⟹ 死循环
    }
}

mid := lo + (hi-lo+1)/2   // 上取整，配合 lo = mid  / hi = mid - 1
mid := lo + (hi-lo)/2     // 下取整，配合 hi = mid  / lo = mid + 1

// 不变式：答案落在半开区间 [lo, hi) 内；a[lo-1] < x ≤ a[hi]
func LowerBound(a []int, x int) int {
    lo, hi := 0, len(a) // 半开区间：hi 可以等于 len(a)
    for lo < hi {       // 半开区间非空的条件是 lo < hi
        mid := lo + (hi-lo)/2
        if a[mid] < x {
            lo = mid + 1 // a[mid] 太小，排除
        } else {
            hi = mid // ⭐ 不是 mid-1：a[mid] 本身可能就是答案
        }
    }
    return lo
}

func UpperBound(a []int, x int) int {
    lo, hi := 0, len(a)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if a[mid] <= x { // 只有这里的 < 改成 <=
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

i := LowerBound(a, x)

存在性：      i < len(a) && a[i] == x
前驱(< x)：   i-1（若 i > 0）
后继(> x)：   UpperBound(a, x)
等于 x 的个数：UpperBound(a, x) - LowerBound(a, x)
范围 [l, r] 内的元素个数：UpperBound(a, r) - LowerBound(a, l)
插入位置（保持有序）：i

i, found := slices.BinarySearch(a, x)     // i 就是 lower_bound，found 是存在性
i := sort.SearchInts(a, x)                // 同上，只返回位置
i := sort.Search(n, func(i int) bool {    // ⭐ 最通用：找第一个使谓词为 true 的 i
    return a[i] >= x                       // 谓词必须单调：false…false,true…true
})

// 判定：每段和都不超过 cap 时，最少需要分几段？≤ k 就可行
func feasible(a []int, k, cap int) bool {
    segs, cur := 1, 0
    for _, x := range a {
        if x > cap {
            return false // 单个元素就超了
        }
        if cur+x > cap {
            segs++ // 开新段（贪心：能装就装）
            cur = x
        } else {
            cur += x
        }
    }
    return segs <= k
}

func SplitArray(a []int, k int) int {
    lo, hi := slices.Max(a), 0 // 下界：最大元素；上界：全部和
    for _, x := range a {
        hi += x
    }
    for lo < hi { // ⭐ 与 LowerBound 完全同构：找第一个 feasible 为 true 的 cap
        mid := lo + (hi-lo)/2
        if feasible(a, k, mid) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}

func BinarySearchReal(feasible func(float64) bool, lo, hi float64) float64 {
    for i := 0; i < 100; i++ { // ⭐ 固定迭代次数，不要用 hi-lo > eps
        mid := lo + (hi-lo)/2
        if feasible(mid) {
            hi = mid
        } else {
            lo = mid
        }
    }
    return lo
}

// [4,5,6,7,0,1,2] —— 有序数组被旋转过，元素互异
func SearchRotated(a []int, x int) int {
    lo, hi := 0, len(a)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if a[mid] == x {
            return mid
        }
        if a[lo] <= a[mid] { // ⭐ 左半段有序
            if a[lo] <= x && x < a[mid] {
                hi = mid - 1
            } else {
                lo = mid + 1
            }
        } else { // 右半段有序
            if a[mid] < x && x <= a[hi] {
                lo = mid + 1
            } else {
                hi = mid - 1
            }
        }
    }
    return -1
}

// 找任意一个 a[i] > a[i-1] && a[i] > a[i+1] 的位置（边界视为 -∞）
func FindPeak(a []int) int {
    lo, hi := 0, len(a)-1
    for lo < hi {
        mid := lo + (hi-lo)/2
        if a[mid] < a[mid+1] {
            lo = mid + 1 // 上坡：右边必有峰
        } else {
            hi = mid // 下坡：左边（含 mid）必有峰
        }
    }
    return lo
}