关于语言：一刷用 Golang，二刷用 Rust

题单来源于：分享丨【题单】二分算法（二分答案/最小化最大值/最大化最小值/第K小）

二分查找

套路

可以把在有序数组上的二分分为四种类型 \(\ge, >, <, \le\)，对于这四种类型都可以互相转换：

• \(>\): \(\ge x + 1\)
• \(<\): \((\ge x) - 1\)
• \(\le\): \((> x) - 1\)

题单

题目	来源	难度	分数
34. 在排序数组中查找元素的第一个和最后一个位置		中等
35. 搜索插入位置		简单
704. 二分查找		简单
744. 寻找比目标字母大的最小字母		简单
2529. 正整数和负整数的最大计数	第 327 场周赛 Q1	简单	1196
1385. 两个数组间的距离值	第 22 场双周赛 Q1	简单	1235
2300. 咒语和药水的成功对数	第 80 场双周赛 Q2	中等	1477
2389. 和有限的最长子序列	第 308 场周赛 Q1	简单	1388
1170. 比较字符串最小字母出现频次	第 151 场周赛 Q2	中等	1432
2080. 区间内查询数字的频率	第 268 场周赛 Q3	中等	1702
2563. 统计公平数对的数目	第 332 场周赛 Q2	中等	1721
2856. 删除数对后的最小数组长度	第 113 场双周赛 Q2	中等	1750
981. 基于时间的键值存储	第 121 场周赛 Q2	中等	1575
1146. 快照数组	第 148 场周赛 Q3	中等	1771
658. 找到 K 个最接近的元素		中等
1818. 绝对差值和	第 235 场周赛 Q3	中等	1934

二分求最小：

题目	来源	难度	分数
1283. 使结果不超过阈值的最小除数	第 166 场周赛 Q3	中等	1542
2187. 完成旅途的最少时间	第 282 场周赛 Q3	中等	1641
1870. 准时到达的列车最小时速	第 242 场周赛	中等	1676
1011. 在 D 天内送达包裹的能力	第 128 场周赛 Q3	中等	1725
875. 爱吃香蕉的珂珂	第 94 场周赛 Q3	中等	1766
3296. 移山所需的最少秒数	第 416 场周赛 Q2	中等	1850
475. 供暖器		中等
2594. 修车的最少时间	第 100 场双周赛 Q4	中等	1915
1482. 制作 m 束花所需的最少天数	第 193 场周赛 Q3	中等	1946

二分求最大：

题目	来源	难度	分数
275. H 指数 II		中等
2226. 每个小孩最多分到	第 287 场周赛 Q3	中等	1646
2982. 找出出现至少三次的最长特殊子字符串 II	第 378 场周赛 Q3	中等	1773
2576. 求出最多标记下标	第 334 场周赛	中等	1843
1898. 可移除字符的最大数目	第 245 场周赛	中等	1913
1802. 有界数组中指定下标处的最大值	第 233 场周赛	中等	1929

题解

34. 在排序数组中查找元素的第一个和最后一个位置

Golang

func searchRange(nums []int, target int) []int {
    check := func(t int) int {
        l, r := 0, len(nums)
        for l < r {
            m := (l + r) >> 1
            if nums[m] < t {
                l = m + 1
            } else {
                r = m
            }
        }
        return l
    }
    a := check(target)
    if a == len(nums) || nums[a] != target {
        return []int{-1, -1}
    }
    b := check(target + 1) - 1
    return []int{a, b}
}

35. 搜索插入位置

Golang

func searchInsert(nums []int, target int) int {
    l, r := 0, len(nums)
    for l < r {
        mid := (l + r) >> 1
        if nums[mid] < target {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

704. 二分查找

Golang

func search(nums []int, target int) int {
    l, r := 0, len(nums)
    for l < r {
        mid := (l + r) >> 1
        if nums[mid] < target {
            l = mid + 1
        } else {
            r = mid
        }
    } 
    if l != len(nums) && nums[l] == target {
        return l
    }
    return -1
}

744. 寻找比目标字母大的最小字母

Golang

func nextGreatestLetter(letters []byte, target byte) byte {
    l, r := 0, len(letters)
    for l < r {
        mid := (l + r) >> 1
        if letters[mid] < target + 1 {
            l = mid + 1
        } else {
            r = mid
        }
    } 
    return letters[l%len(letters)]
}

2529. 正整数和负整数的最大计数

Golang

func maximumCount(nums []int) int {
    check := func(t int) int {
        l, r := 0, len(nums)
        for l < r {
            mid := (l + r) >> 1
            if nums[mid] < t {
                l = mid + 1
            } else {
                r = mid
            }
        }
        return l
    }
    pos, neg := len(nums) - check(1), check(0)
    return max(pos, neg)
}

1385. 两个数组间的距离值

Golang

func findTheDistanceValue(arr1 []int, arr2 []int, d int) (ans int) {
    sort.Ints(arr2)
    f := func(v int) int {
        l, r := 0, len(arr2)
        for l < r {
            mid := (l + r) >> 1
            if arr2[mid] < v {
                l = mid + 1
            } else {
                r = mid
            }
        }
        return l
    }
    for _, a := range arr1 {
        // 找 > d 的 < d 的两个位置
        if f(a + d + 1) - f(a - d) <= 0 {
            ans++
        }
    } 
    return
}

func abs(v int) int {
    if v < 0 { return -v }
    return v
}

2300. 咒语和药水的成功对数

Golang

func successfulPairs(spells []int, potions []int, success int64) []int {
    sort.Ints(potions)
    n, m := len(spells), len(potions)
    ans := make([]int, n)
    for k, s := range spells {
        l, r := 0, m
        for l < r {
            mid := (l + r) >> 1
            if int64(s) * int64(potions[mid]) < success {
                l = mid + 1
            } else {
                r = mid
            }
        }
        ans[k] = m - l
    }
    return ans
}

2389. 和有限的最长子序列

Golang

func answerQueries(nums []int, queries []int) []int {
    sort.Ints(nums)
    n, m := len(nums), len(queries)
    for i := 1; i < n; i++ {
        nums[i] += nums[i-1]
    } 
    ans := make([]int, m)
    for k, q := range queries {
        l, r := 0, n
        for l < r {
            mid := (l + r) >> 1
            if nums[mid] < q + 1 {
                l = mid + 1
            } else {
                r = mid
            }
        }
        ans[k] = l
    }
    return ans
}

1170. 比较字符串最小字母出现频次

Golang

func numSmallerByFrequency(queries []string, words []string) []int {
    n, m := len(queries), len(words)
    ans := make([]int, n)
    f := func(s string) int {
        cnt := [26]int{}
        for _, v := range s {
            cnt[v-'a']++
        }
        for _, v := range cnt {
            if v == 0 {
                continue
            }
            return v
        }
        return 0
    }
    cnt := make([]int, m)
    for k, v := range words {
        cnt[k] = f(v)
    }
    sort.Ints(cnt)
    for k, v := range queries {
        l, r := 0, m
        target := f(v)
        for l < r {
            mid := (l + r) >> 1
            if cnt[mid] < target + 1 {
                l = mid + 1
            } else {
                r = mid
            }
        }
        ans[k] = m - l
    }
    return ans
}

2080. 区间内查询数字的频率

Golang

type RangeFreqQuery struct {
    index map[int][]int
}


func Constructor(arr []int) RangeFreqQuery {
    index := make(map[int][]int)
    for i, v := range arr {
        if index[v] == nil {
            index[v] = make([]int, 0)
        }
        index[v] = append(index[v], i)
    }
    return RangeFreqQuery{index}
}

func (this *RangeFreqQuery) find(pos, value int) int {
    idx := this.index[value]
    l, r := 0, len(idx)
    for l < r {
        mid := (l + r) >> 1
        if idx[mid] < pos + 1 {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l - 1
}

func (this *RangeFreqQuery) Query(left int, right int, value int) int {
    return this.find(right, value) - this.find(left - 1, value)
}

2563. 统计公平数对的数目

排序不影响答案，然后枚举 \(nums[j]\)，\(nums[i]\) 需要满足

\[lower - nums[j] \le nums[i] \le upper - nums[j]\]

Golang

func countFairPairs(nums []int, lower int, upper int) (ans int64) {
    sort.Ints(nums)
    f := func(i, target int) int64 {
        l, r := 0, i
        for l < r {
            mid := (l + r) >> 1
            if nums[mid] < target {
                l = mid + 1
            } else {
                r = mid
            }
        }
        return int64(l)
    }
    for i, num := range nums {
        ans += f(i, upper - num + 1) - f(i, lower - num)
    }
    return
}

2856. 删除数对后的最小数组长度

假设 \(x\) 出现次数最多，出现次数为 \(maxCnt\)

• 如果 \(maxCnt \cdot 2 > n\) 其余 \(n - maxCnt\) 个数都要与 \(x\) 消除，最后剩下 \(maxCnt \cdot 2 - n\) 个数。
• 如果 \(maxCnt \cdot 2 \le n\) 且 \(n\) 是偶数，那么可以把其余数消除至剩下 \(maxCnt\) 个数，然后再和 \(x\) 消除。最后剩下 \(0\) 个数。
• 如果 \(maxCnt \cdot 2 \le n\) 且 \(n\) 是奇数，最后剩下一个数。

由于 \(nums\) 是有序的，如果 \(maxCnt\) 超过数组长度的一半，那么 \(nums[n/2]\) 一定是出现次数最多的那个数。

Golang

func minLengthAfterRemovals(nums []int) int {
    n := len(nums)
    x := nums[n/2]
    maxCnt := sort.SearchInts(nums, x + 1) - sort.SearchInts(nums, x)
    return max(maxCnt * 2 - n, n % 2)
}

981. 基于时间的键值存储

Golang

type TimeMap struct {
    index map[string][]int
    value map[string][]string
}


func Constructor() TimeMap {
    return TimeMap{
        index: map[string][]int{},
        value: map[string][]string{},
    } 
}


func (this *TimeMap) Set(key string, value string, timestamp int)  {
    this.index[key] = append(this.index[key], timestamp)
    this.value[key] = append(this.value[key], value)
}


func (this *TimeMap) Get(key string, timestamp int) string {
    idx := sort.SearchInts(this.index[key], timestamp + 1) - 1
    if idx == -1 || idx == len(this.index[key]) {
        return ""
    }
    return this.value[key][idx]
}

1146. 快照数组

Golang

type SnapshotArray struct {
    index [][]int
    value [][]int
    snapId int
}


func Constructor(length int) SnapshotArray {
    return SnapshotArray{
        index: make([][]int, length),
        value: make([][]int, length),
        snapId: 0,
    }
}


func (this *SnapshotArray) Set(index int, val int)  {
    this.index[index] = append(this.index[index], this.snapId)
    this.value[index] = append(this.value[index], val)
}


func (this *SnapshotArray) Snap() int {
    this.snapId++
    return this.snapId - 1
}


func (this *SnapshotArray) Get(index int, snap_id int) int {
    idx := sort.SearchInts(this.index[index], snap_id + 1) - 1
    if idx >= 0 {
        return this.value[index][idx]
    }
    return 0
}

658. 找到 K 个最接近的元素

Golang

func findClosestElements(arr []int, k int, x int) []int {
    right := sort.SearchInts(arr, x)
    left := right - 1
    for ; k > 0; k-- {
        if left < 0 {
            right++
        } else if right >= len(arr) || x - arr[left] <= arr[right] - x {
            left--
        } else {
            right++
        }
    } 
    return arr[left+1 : right]
}

1818. 绝对差值和

单个二元组 \((nums_1[i], nums_2[i])\) 对答案的贡献为 \(\left| nums_1[i] - nums_2[i] \right|\)。假设用元素 \(nums_1[j]\) 替换了元素，那么此时二元组对答案的贡献为 \(\left| nums_1[j] - nums_2[i] \right|\)。改变前后的差值为：

\[\left | nums_1[i] - nums_2[i] \right | - \left| nums_1[j] - nums_2[i] \right|\]

最大化该值，这样可以使的答案尽可能小，因为只能修改一个位置，所以需要检查每一个 \(i\) 对应的差值的最大值。当 \(i\) 确定，式子的前半部分可以确定，后半部分取决于 \(j\) 的选择。只需要找到和 \(nums_2[i]\) 相近的 \(nums_1[j]\) 即可。

Golang

func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
    a := make([]int, len(nums1))
    copy(a, nums1)
    sort.Ints(a)
    sum, maxn, n := 0, 0, len(nums1)
    for i, v := range nums2 {
        diff := abs(nums1[i] - v)
        sum += diff
        j := sort.SearchInts(a, v)
        if j < n {
            maxn = max(maxn, diff - (a[j] - v))
        }
        if j > 0 {
            maxn = max(maxn, diff - (v - a[j-1]))
        }
    }
    return (sum - maxn) % (1e9 + 7)
}

func abs(v int) int {
    if v < 0 { return -v }
    return v
}

1283. 使结果不超过阈值的最小除数

Golang

func smallestDivisor(nums []int, threshold int) int {
    l, r := 1, 1000000
    for l < r {
        mid := (l + r) >> 1
        sum := 0
        for _, v := range nums {
            sum += (v + mid - 1) / mid
        }
        fmt.Println(sum)
        if sum > threshold {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

2187. 完成旅途的最少时间

Golang

func minimumTime(time []int, totalTrips int) int64 {
    sort.Ints(time)
    n := len(time)
    l, r := int64(1), int64(time[n-1] * totalTrips)
    check := func(t int64) bool {
        cnt := 0
        for _, v := range time {
            cnt += int(t / int64(v))
        }
        return cnt < totalTrips
    }
    for l < r {
        mid := (l + r) >> 1
        if check(mid) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

1870. 准时到达的列车最小时速

Golang

func minSpeedOnTime(dist []int, hour float64) int {
    l, r := 1, 10000001
    check := func(speed int) bool {
        s := float64(0)
        for i, v := range dist {
            if i != len(dist) - 1 {
                s += math.Ceil(float64(v) / float64(speed))
            } else {
                s += float64(v) / float64(speed)
            }
        }
        return s > hour
    }
    for l < r {
        mid := (l + r) >> 1
        if check(mid) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    if l >= 10000001 {
        return -1
    }
    return l
}

1011. 在 D 天内送达包裹的能力

Golang

func shipWithinDays(weights []int, days int) int {
    n := len(weights)
    l, r := math.MinInt, 500 * n 
    for _, v := range weights {
        l = max(l, v)
    }
    check := func(w int) bool {
        s, d := 0, 0
        for _, v := range weights {
            if s + v > w {
                s = 0
                d++
            }
            s += v
        }
        if s > 0 {
            d++
        }
        return d > days
    }
    for l < r {
        mid := (l + r) >> 1
        if check(mid) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

875. 爱吃香蕉的珂珂

Golang

func minEatingSpeed(piles []int, h int) int {
    l, r := 1, int(1e9 + 10)
    check := func(speed int) bool {
        cnt := 0
        for _, p := range piles {
            cnt += int(math.Ceil(float64(p) / float64(speed)))
        }
        return cnt > h
    }
    for l < r {
        mid := (l + r) >> 1
        if check(mid) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

3296. 移山所需的最少秒数

Golang

func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {
    l, r := int64(1), int64(1e18)
    //  通过二分，计算每个工人在 t 的时间内能降低多少高度
    check := func(t int64) bool {
        s := 0
        for _, v := range workerTimes {
            l, r := 0, mountainHeight
            for l < r {
                mid := (l + r + 1) >> 1
                if int64((1 + mid) * mid / 2 * v) <= t {
                    l = mid
                } else {
                    r = mid - 1
                }
            }
            s += l
            if s >= mountainHeight {
                break
            }
        }
        return s < mountainHeight
    }
    for l < r {
        mid := (l + r) >> 1
        if check(mid) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return int64(l)
}

475. 供暖器

Golang

func findRadius(houses []int, heaters []int) int {
    sort.Ints(houses)
    sort.Ints(heaters)
    check := func(rad int) bool {
        i, j := 0, 0
        for i < len(houses) && j < len(heaters) {
            if houses[i] >= heaters[j] - rad && houses[i] <= heaters[j] + rad {
                i++
            } else {
                j++
            }
        }
        return i < len(houses)
    }
    l, r := 0, int(1e9)
    for l < r {
        mid := (l + r) >> 1
        if check(mid) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

2594. 修车的最少时间

Golang

func repairCars(ranks []int, cars int) int64 {
    mn := slices.Min(ranks)
    l, r := int64(1), int64(mn * cars * cars)
    check := func(t int64) bool {
        s := 0
        for _, rank := range ranks {
            s += int(math.Sqrt(float64(t / int64(rank))))
        }
        return s < cars
    }
    for l < r {
        mid := (l + r) >> 1
        if check(mid) {
            l = mid + 1
        } else {
            r = mid
        }
    } 
    return l
}

1482. 制作 m 束花所需的最少天数

Golang

func minDays(bloomDay []int, m int, k int) int {
    if m * k > len(bloomDay) {
        return -1
    }
    mx := slices.Max(bloomDay)
    l, r := 0, mx
    check := func(day int) bool {
        s, cnt := 0, 0
        for _, b := range bloomDay {
            if b > day {
                cnt = 0
            } else {
                cnt++
            }
            if cnt == k {
                s++
                cnt = 0
            }
        }
        return s < m
    }
    for l < r {
        mid := (l + r) >> 1
        if check(mid) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

275. H 指数 II

Golang

func hIndex(citations []int) int {
    sort.Ints(citations)
    n := len(citations)
    l, r := 1, n + 1
    for l < r {
        mid := (l + r) >> 1
        if citations[n - mid] >= mid {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l - 1
}

2226. 每个小孩最多分到

Golang

func maximumCandies(candies []int, k int64) int {
    l, r := 1, slices.Max(candies) + 1
    check := func(t int) bool {
        cnt := int64(0)
        for _, v := range candies {
            cnt += int64(v / t)
        }
        return cnt >= k
    }
    for l < r {
        mid := (l + r) >> 1
        if check(mid) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l - 1
}

2982. 找出出现至少三次的最长特殊子字符串 II

如果一个长度为 \(x\) 且出现次数至少三次的特殊子字符串存在，那么长度为 \(x-1\) 的特殊子字符串也一定存在，这意味着答案存在单调性，可以使用二分查找的方法来找到最长的特殊子字符串。

Golang

func maximumLength(s string) int {
    n := len(s)
    l, r := 0, len(s) 
    check := func(length int) bool {
        cnt := [26]int{}
        for i := 0; i < n; {
            j := i + 1;
            for j < n && s[j] == s[i] {
                j++
            }
            k := s[i] - 'a'
            cnt[k] += max(0, j - i - length + 1)
            if cnt[k] >= 3 {
                return true
            }
            i = j
        }
        return false
    }
    for l < r {
        mid := (l + r + 1) >> 1
        if check(mid) {
            l = mid
        } else {
            r = mid - 1
        }
    }
    if l == 0 {
        return -1
    }
    return l
}

2576. 求出最多标记下标

Golang

func maxNumOfMarkedIndices(nums []int) int {
    n := len(nums)
    sort.Ints(nums)
    l, r := 0, n / 2
    check := func(cnt int) bool {
        for i := 0; i < cnt; i++ {
            if 2 * nums[i] > nums[n - cnt + i] {
                return false
            }
        }
        return true
    }
    for l < r {
        mid := (l + r + 1) >> 1
        if check(mid) {
            l = mid
        } else {
            r = mid - 1
        }
    }
    return 2 * l
}

1898. 可移除字符的最大数目

Golang

func maximumRemovals(s string, p string, removable []int) int {
    n := len(removable)
    l, r := 0, n
    check := func(k int) bool {
        bs, bp := []byte(s), []byte(p)
        for i := 0; i < k; i++ {
            bs[removable[i]] = '.'
        }
        i, j := 0, 0
        for i < len(s) && j < len(p) {
            if bs[i] == bp[j] {
                j++
            }
            i++
        }
        return j == len(p)
    }
    for l < r {
        mid := (l + r + 1) >> 1
        if check(mid) {
            l = mid
        } else {
            r = mid - 1
        }
    } 
    return l
}

1802. 有界数组中指定下标处的最大值

Golang

func maxValue(n int, index int, maxSum int) int {
    l, r := 1, maxSum
    sum := func(x, idx int) int {
        if idx == 0 {
            return 0
        }
        if idx <= x {
            return (2 * x + 1 - idx) * idx / 2
        }
        return (x + 1) * x / 2 + idx - x
    }
    check := func(num int) bool {
        return num + sum(num, index) + sum(num, n - index - 1) < maxSum
    }
    for l < r {
        mid := (l + r) >> 1
        if check(mid) {
            l = mid + 1
        } else {
            r = mid
        }
    } 
    return l
}

1. 1. 二分查找
   1. 1.1. 套路
   2. 1.2. 题单
   3. 1.3. 题解
      1. 1.3.1. 34. 在排序数组中查找元素的第一个和最后一个位置
      2. 1.3.2. 35. 搜索插入位置
      3. 1.3.3. 704. 二分查找
      4. 1.3.4. 744. 寻找比目标字母大的最小字母
      5. 1.3.5. 2529. 正整数和负整数的最大计数
      6. 1.3.6. 1385. 两个数组间的距离值
      7. 1.3.7. 2300. 咒语和药水的成功对数
      8. 1.3.8. 2389. 和有限的最长子序列
      9. 1.3.9. 1170. 比较字符串最小字母出现频次
      10. 1.3.10. 2080. 区间内查询数字的频率
      11. 1.3.11. 2563. 统计公平数对的数目
      12. 1.3.12. 2856. 删除数对后的最小数组长度
      13. 1.3.13. 981. 基于时间的键值存储
      14. 1.3.14. 1146. 快照数组
      15. 1.3.15. 658. 找到 K 个最接近的元素
      16. 1.3.16. 1818. 绝对差值和
      17. 1.3.17. 1283. 使结果不超过阈值的最小除数
      18. 1.3.18. 2187. 完成旅途的最少时间
      19. 1.3.19. 1870. 准时到达的列车最小时速
      20. 1.3.20. 1011. 在 D 天内送达包裹的能力
      21. 1.3.21. 875. 爱吃香蕉的珂珂
      22. 1.3.22. 3296. 移山所需的最少秒数
      23. 1.3.23. 475. 供暖器
      24. 1.3.24. 2594. 修车的最少时间
      25. 1.3.25. 1482. 制作 m 束花所需的最少天数
      26. 1.3.26. 275. H 指数 II
      27. 1.3.27. 2226. 每个小孩最多分到
      28. 1.3.28. 2982. 找出出现至少三次的最长特殊子字符串 II
      29. 1.3.29. 2576. 求出最多标记下标
      30. 1.3.30. 1898. 可移除字符的最大数目
      31. 1.3.31. 1802. 有界数组中指定下标处的最大值