Python 3バイナリ検索でソートされた変数（数値のリスト）

Question

こんにちはそこに：私はソートされたリストを使ってバイナリ検索を使用するプログラムを書いていました。次のようにそれが動作するはずです：それは1 2としている場合、プログラムは数字に3を探す必要があります3 1 2 3

のpython find.py 1 2及び3

それは本当と印刷見つかった針を返す必要があります3、 falseを返す必要がありますし、印刷が見つからなかった場合、それは1 2と3にない場合は....

def binary_search(needle, haystack): 
first = 0 
last = len(haystack) - 1 
itemlist = str(input(haystack)) 
sorted(itemlist) 

while first <= last: 
    mid = (first + last)/2 
    if itemlist[mid] == needle : 
     print("Found the needle in the haystack") 
     return True 
    elif needle < itemlist[mid]: 
     last = mid - 1 
    else: 
     first = mid + 1 
    if not True: 
     print("Did not find the needle in the haystack") 
     return False 

ので、私は、標準のバイナリサーチアルゴリズムを実装しようとしたが、私が渡って来るすべてのバージョンにはありませんあなたが来るすべての番号で検索する必要がある項目として最初の番号を取る... 私の質問は、どのように私は何ですか最初の変数を「アイテム」とし、アイテムを含むかもしれないし、含まないかもしれないリストとして来るものはどれですか？

また、xの長さのリストをソートする必要があります。ソートされた関数を試しましたが、リストは任意の長さにできるので、変数をソートする必要がありますか？私はちょっとそこにこだわっています....これらの話題に関するヒント？

Answer 1

sys.argvは、pythonプロセスを呼び出すために使用されるコマンドライン引数を含むリストです。 sys.argv[0]はスクリプトの名前であり、残りの引数はsys.arv[1:]です。

def binary_search(needle, haystack): 
    print('binary_search(): needle = {}, haystack = {}'.format(needle, haystack)) 
    # your implementation here 

if __name__ == '__main__': 
    import sys 

    if len(sys.argv) > 2: 
     needle = sys.argv[1] 
     haystack = sys.argv[2:] 
     binary_search(needle, haystack) 
    else: 
     print('Usage: {} needle haystack...'.format(sys.argv[0])) 

---

あなたは、最初の干し草の山を並べ替えるsorted()を使用する必要がある場合：

binary_search(needle, sorted(haystack)) 

しかし、最初の並べ替えに少しポイントがあることがO（n個を持っているので、このようなアクセスをlog n）時間の複雑さ、一方、線形探索は、O（n）時間の複雑さしか持たない。したがって、入力がソートされていない場合は、ターゲットが見つかるまでリストを反復して検索するほうがよいでしょう。

---

最後に、検索を機能させるには、入力を数値に変換する必要があります。

Answer 2

バイナリ検索は標準ライブラリの一部です。この場合、int()を使用できます。

import sys 
import bisect 

argv = [int(_) for _ in sys.argv[1:]] 
x = argv.pop(0) 
i = bisect.bisect_left(argv, x) 
print("Found:", i != len(argv) and argv[i] == x) 

また、入力リストが既にソートされている場合にのみ問題が発生します。そうでない場合は、単にx in argvを使用します（リストをソートすることは直線的です）。