Python中的二進(jìn)制搜索(二分法)是否有一個(gè)庫函數(shù)可以對列表/元組執(zhí)行二進(jìn)制搜索，如果找到并返回項(xiàng)的位置和‘false’(-1，無，等等)如果不是？我在平分模，但即使項(xiàng)目不在列表中，它們?nèi)匀环祷匾粋€(gè)位置。對于它們的預(yù)期用途來說，這是非常好的，但我只想知道列表中是否有項(xiàng)目(不想插入任何內(nèi)容)。我想用bisect_left然后檢查位于該位置的項(xiàng)是否等于我正在搜索的內(nèi)容，但這似乎很麻煩(我還需要進(jìn)行邊界檢查，以檢查該數(shù)字是否可以大于我列表中最大的數(shù)字)。如果有更好的方法，我想知道。編輯為了澄清我需要它做什么：我知道字典將非常適合這一點(diǎn)，但我正試圖盡可能地降低內(nèi)存消耗。我打算用的是一張雙向查表。表中有一個(gè)值列表，我需要能夠根據(jù)它們的索引訪問這些值。另外，我希望能夠找到某個(gè)特定值的索引，如果該值不在列表中，則為零。為此使用字典將是最快的方法，但將(大約)增加一倍的內(nèi)存需求。我在問這個(gè)問題時(shí)認(rèn)為，我可能忽略了Python庫中的一些內(nèi)容?？磥砦业米约簩懘a了，就像Moe建議的那樣。
3 回答
炎炎設(shè)計(jì)
TA貢獻(xiàn)1808條經(jīng)驗(yàn) 獲得超4個(gè)贊
from bisect import bisect_leftdef binary_search(a, x, lo=0, hi=None): # can't use a to specify default for hi hi = hi if hi is not None else len(a) # hi defaults to len(a) pos = bisect_left(a, x, lo, hi) # find insertion position return (pos if pos != hi and a[pos] == x else -1) # don't walk off the end
呼如林
TA貢獻(xiàn)1798條經(jīng)驗(yàn) 獲得超3個(gè)贊
def binary_search(a, x, lo=0, hi=None): if hi is None: hi = len(a) while lo < hi: mid = (lo+hi)//2 midval = a[mid] if midval < x: lo = mid+1 elif midval > x: hi = mid else: return mid return -1
添加回答
舉報(bào)
0/150
提交
取消