11.3 在数值范围内二分查找

使用二分查找的要点:

• 解的范围确定, 即解的最大/小值已知
• 每次都能将范围缩小一半

11.3.1 问题72: 平方根

LCR 072. x 的平方根

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

示例 1:

输入: x = 4
输出: 2

示例 2:

输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2

提示:

• 0 <= x <= 2^31 - 1

11.3.1.1 分析&题解

对于整数n,若不为0, 其正数平方根m 取值范围为[1, n], 且满足 $m^2 \le n, (m+1)^2 > n$

那么可以使用二分查找来求平方根.

func mySqrt(x int) int {
    left, right := 1, x
    for left <= right {
        mid := (left + right) / 2
        
        if mid <= x/mid {
            if mid+1 > x/(mid+1) {
                return mid
            }

            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return 0
}

11.3.2 问题73: 狒狒吃香蕉

LCR 073. 爱吃香蕉的狒狒

狒狒喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

狒狒可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。

狒狒喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例 1：

输入: piles = [3,6,7,11], H = 8
输出: 4

示例 2：

输入: piles = [30,11,23,4,20], H = 5
输出: 30

示例 3：

输入: piles = [30,11,23,4,20], H = 6
输出: 23

提示：

• 1 <= piles.length <= 10^4
• piles.length <= H <= 10^9
• 1 <= piles[i] <= 10^9

11.3.2.1 分析&题解

猩猩每小时吃的个数范围为: [1, maxPile], maxPile是堆中最大的香蕉数目.

使用二分查找寻找吃香蕉的最小速度, 其满足速度为mid 时间小于等于H 并且 mid-1时间大于H.

func minEatingSpeed(piles []int, h int) int {
	// find max pile
	maxPile := math.MinInt
	for _, p := range piles {
		if p > maxPile {
			maxPile = p
		}
	}

	// binary search
	left, right := 1, maxPile
	for left <= right {
		mid := (left + right) / 2

		// 能吃完
		if getTime(piles, mid) <= h {
			// 速度 1 或 能吃完的最小速度
			if mid == 1 || getTime(piles, mid-1) > h {
				return mid
			}

			// 减小速度
			right = mid - 1
		} else {
			// 加大速度
			left = mid + 1
		}
	}

	return -1
}

func getTime(piles []int, speed int) int {
	t := 0
	for _, p := range piles {
		if p % speed == 0 {
			t += p/speed
		} else {
			t += p/speed + 1
		}
	}
	return t
}

Reference

1. 剑指Offer（专项突破版）