二分法解题模板

二分法

今天重新审视了二分法,结合同事的思考认为,

二分的本质是,在一段或多段单调序列里找分界点

使用左开右闭 [l, r) 的模板如下:

1
2
3
4
5
6
7
8
9
def binary_search(l, r):
while l < r:
m = l + (r - l) // 2
if f(m): return m # optional
if g(m):
r = m # new range [l, m)
else:
l = m + 1 # new range [m+1, r)
return l # or not found

m 如果满足查找条件,即 f(m) 返回 true,则查找结束。如果 f(m) 返回 false, 则根据 g(m) 的结果构造新的查找区间。如果新区间在左边,则新的左闭右开区间是 [l, m) 等价于 [l, m-1];如果新区间在右边,则新的左闭右开是 [m+1, r)

Return the lower_bound / upper_bound of a value x in a sorted array.

lower_bound(A, x): first index of i, such that A[i] >= x

1
2
3
4
5
6
7
8
def lower_bound(A, x, l, r):
while l < r:
m = (l + r) // 2
if A[m] >= x:
r = m
else:
l = m + 1
return l

if A[m] == x, still need to update right bound to m as there are probable mutiple x at the left of m.

upper_bound(A, x): first index of i, such that A[i] > x

1
2
3
4
5
6
7
8
def upper_bound(A, x, l, r):
while l < r:
m = (l + r) // 2
if A[m] > x:
r = m
else:
l = m + 1
return l

案例应用

案例 1:Capacity to Ship Packages Within D Days

https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def shipWithinDays(self, weights: List[int], D: int) -> int:

l, r = max(weights), sum(weights)

while l < r:
m = (l + r) // 2

s = 0
rounds = 1
for i in range(len(weights)):
if s + weights[i] <= m:
s += weights[i]
else: # overload, need next round
s = weights[i]
rounds += 1

if rounds <= D:
r = m
else:
l = m + 1

return l

案例 2:Coko Eating Bananas

https://leetcode.com/problems/koko-eating-bananas/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def minEatingSpeed(self, piles: List[int], H: int) -> int:
l, r = 1, max(piles) + 1

while l < r:
m = l + (r - l) // 2

time = 0
for x in piles:
time += math.ceil(x / m)
if time <= H:
r = m
else:
l = m + 1

return l

本文标题:二分法解题模板

文章作者:Pylon, Syncher

发布时间:2019年10月24日 - 19:10

最后更新:2023年09月26日 - 10:09

原始链接:https://0x400.com/fundamental/algorithm/lc-binary-search-template/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。