python - リストを二等分するPython

Question

リストを取得してそれを二等分する関数を作成する必要があります (bisect モジュールのように使用できません)。私は通常、これまでに行ったことを示しますが、モジュールなしでそれを行う方法が本当にわからないので、誰かが私を少し助けてくれることを願っています. これが私が理解する必要がある正確な質問です：

並べ替えられたリストとターゲット値を受け取り、リスト内の値のインデックスがあればそれを返し、そうでない場合は None を返す bisect という関数を作成します。

Answer 1

私は「python を考える」の第 10 章の演習 8 の宿題をしていて、fred によって書かれた上記のコードにうんざりしていました。いくつかのバグがあるようです。1. カウンターは 100k 文字列の長いリストでは機能しません。

だから私はそれを少し微調整しました：

これは私のバージョンです:

それは非常にうまく機能し、最初はmobyコレクションから来たwords.txtという名前のswampy 2.0のワードリストでテストしました：113809of.fic

これが bisect プログラムに苦労しているあなたの助けになることを願っています

def bisects (list,x,counter=0):

    if len(list)==0:
        return x,'is not in the list'
    elif(len(list)==1):
        middle = 0
    else:
        middle = int(len(list)/2)

    if x == list[middle]:
        return counter, x,'is in the list' 
    elif x < list[middle]:
        counter +=0
        return bisects(list[0:middle],x,counter)
    elif x > list[middle]:
        counter +=middle
        return bisects(list[middle+1:],x,counter) 

また、教祖がその欠陥を修正するのを手伝ってくれるなら素晴らしいでしょう、ありがとう、

Answer 2

bisect モジュールは、要素を挿入するたびに頼ることなく、リストを追跡し、ソートしたままにします。実装する必要があるメソッドは、ソートされたリスト内を検索するだけです。

def bisect(sortedlist,targetvalue,firstindex=0,lastindex=None):

    if(len(sortedlist)==0):
        return None
    if(len(sortedlist)==1):
        if(sortedlist[0]==targetvalue):
            return firstindex
        else:
            return None
    center = int(round(len(sortedlist)/2))

    if(sortedlist[center]==targetvalue):
        return firstindex+center
    if(targetvalue>sortedlist[center]):
        return bisect(sortedlist[center+1:lastindex],targetvalue,center+1,lastindex)
    else:
        return bisect(sortedlist[0:center],targetvalue,firstindex,center-1)

これは基本的に二分探索を行います。インデックスは、再帰ループのさらに下の呼び出しで、元のリストのインデックスを追跡するために渡されます。