最近我在玩二進制搜索演算法。我更喜歡以 while lo < hi.
今天遇到一個問題，讓我更困惑了。leetcode 問題是給定一個整數陣列ribbons，其中ribbons[i] 代表第i 個色帶的長度，以及一個整數k。您可以將任何條帶切割成任意數量的正整數段，或者根本不進行切割。目標是獲得所有相同正整數長度的 k 個色帶。由于切割，您可以丟棄任何多余的色帶。回傳您可以獲得 k 個色帶的最大可能正整數長度，如果無法獲得 k 個相同長度的色帶，則回傳 0。示例輸入和輸出是：
Input: ribbons = [7,5,9], k = 4
Output: 4
此代碼可以回傳所需的結果，并且它使用的是 high mid：
class Solution(object):
def maxLength(self, ribbons, k):
s = sum(ribbons)
if s//k == 0:
return 0
lo, hi = 1, s//k
def bs(cut):
return sum([r//cut for r in ribbons]) >= k
while lo < hi:
mid = (lo hi 1)//2
if bs(mid):
lo = mid
else:
hi = mid-1
return lo
此代碼也可以給出正確答案，但使用下中頻：
class Solution(object):
def maxLength(self, ribbons, k):
s = sum(ribbons)
if s < k: return 0
def bs(cut):
return sum([r // cut for r in ribbons]) >= k
lo, hi = 1, s//k
while lo <= hi:
mid = (lo hi) // 2
if bs(mid):
lo = mid 1
else:
hi = mid - 1
return hi
我的問題是，如何決定何時使用高中音或低中音？在什么情況下應該回傳lo或hi？這真的讓我很困惑。任何幫助表示贊賞。
uj5u.com熱心網友回復：
你的一個實作壞了:)
最終，四舍五入的選擇mid取決于你過低的過牌還是過高的過牌。
在你的情況下，bs(mid)是一個過高的檢查，所以你if應該是這樣的：
if bs(mid):
# not too high (correct answer is >=)
lo = mid
else
# too high (correct answer is <)
hi = mid-1
因為你有一個太高的檢查，可能的下一個邊界是mid和mid-1。如果您的支票過低，則可能性是mid 1和mid。
為了保證每次迭代的范圍變小（避免無限回圈），并且lo <= hi始終需要lo <= mid-1 < mid <= hi. 鑒于此lo < hi，這是由mid = lo (hi-lo 1)//2-- 向上舍入保證的。
如果您的支票太低，那么您將需要那個lo <= mid < mid 1 <= hi。隨著lo < hi，由保證mid = lo (hi-lo)//2。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/374298.html
上一篇：匹配隊友偏好的演算法
下一篇：Python平分：值的搜索范圍