バイナリ検索プログラム

Question

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)) 

バイナリ検索アルゴリズムです。私には2つの質問があります。

質問1： firstが次の行に必要なのはなぜですか？

mid = first + (last - first)/2 

質問2： 私はプログラムを実行したとき、私は、結果を実行することはできません。 エラーメッセージは次のとおりです。

range indices must be integers or slices, not float. 

私はそれを解決できますか？

Answer 1

質問2：で始まる

エラーメッセージ「レンジ指数が整数またはスライスでなければならない、浮いていないが、」あなたはsome_list[5:]で例えば、リストのようなコレクションの一部を取得（スライスしようとしていることを示しています）intではなくfloatを使用します。正確には、midは5ではなく5.0です。

Python 3では、デフォルトの除算は浮動除算です（Python 2と異なります）。整数除算を得るには、ダブルスラッシュ演算子を使用する必要があります。

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

質問1について：midは中間要素です。中間要素を得るのは初等方程式ですが、他の等価方程式を期待していたので混乱しているかもしれません。あなたは、各再帰呼び出しでリストsのコピーを作成し、実装を使用していた場合の方程式は異なる可能性が

mid = (first + last) // 2 

：

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

かのように計算することができます。あなたが提供した実装は "インプレース"で動作し、絶対座標が必要です。

EDIT：@philipxyのコメントで指摘されているように、スライス関連のエラーの原因を簡単に見つけることができ、エラーメッセージ "division"を検索できます。

これをテストしたところ、最初のGoogleの結果はTypeError: list indices must be integers, not floatになりました。これはあなたのものと全く同じ問題（バイナリ検索）であるため、この質問には重複としてフラグを付けて、ここに2番目の質問が含まれていなければ閉じます。事実、経験豊富なユーザーは重複していると判断することがあります。