二進制搜索程序

-1

def bsearch(s, e, first, last): 
    print(first, last) 
    if (last - first) < 2: 
     return s[first] == e or s[last] == e 
    mid = first + (last - first)/2 
    if s[mid] == e: return True 
    if s[mid] > e: return bsearch(s, e, first, mid - 1) 
    return bsearch(s, e, mid + 1, last) 

def search1(s,e): 
    print(bsearch(s, e, 0, len(s)-1)) 
    print('Search complete') 

def testSearch(): 
    s = range(0, 1000000) 
    input('binary,-1') 
    print(search1(s, -1))

它是二進制搜索算法。我有兩個問題。二進制搜索程序

問題1：爲什麼在以下行中需要first？

mid = first + (last - first)/2

問題2：我不能運行的結果，當我跑的程序。的錯誤信息是：

range indices must be integers or slices, not float.

我怎樣才能解決呢？

來源

2017-08-01 Sunner

當你使用'python 3 float'，'python 3 range function'和你的錯誤信息時，你發現了什麼？ – philipxy

與問題2起：

消息錯誤「索引範圍必須是整數或片，不浮」告訴你，你正試圖切片（得到一個類似列表的集合的一部分，例如用some_list[5:] ）使用float，而不是int。更確切地說，您的mid是5.0，而不是5。

在Python 3中，默認的劃分是浮動除法（與Python 2不同）。要獲得整數除法，您需要使用雙斜槓運算符：

mid = first + (last - first) // 2

關於問題1：mid是中間元素。獲得中間元素是基本方程，但也許你會因爲期待另一個等價方程而感到困惑;它可以計算爲

mid = first + (last - first) // 2

或：

mid = (first + last) // 2

如果你使用它在每次遞歸調用創建列表s拷貝實現的公式可能會有所不同。你提供的實現工作「就地」，所以它需要絕對座標。

編輯：如@ philipxy在註釋中指出的那樣，您可以輕鬆找到導致與切片有關的錯誤的原因，並搜索錯誤消息+「division」。

我剛剛測試過這個，第一個Google結果指向TypeError: list indices must be integers, not float;因爲這與您的問題完全相同（二進制搜索），如果不是您的第二個問題，此問題可能會被標記爲重複並關閉。事實上，一些更有經驗的用戶仍然可以決定將其標記爲重複。

來源

2017-08-01 10:53:27 krassowski

二進制搜索程序

回答

相關問題