Pythonリストのバイナリ検索

Question

私はPythonでリストのバイナリ検索を実行しようとしています。リストはコマンドライン引数を使用して作成されます。ユーザーは配列内で検索したい番号を入力し、要素のインデックスを返します。何らかの理由で、プログラムは1とNoneのみを出力します。コードは以下のとおりです。 ご迷惑をおかけして申し訳ございません。コメントに書かれたよう

import sys 

def search(list, target): 
    min = 0 
    max = len(list)-1 
    avg = (min+max)/2 
    while (min < max): 
    if (list[avg] == target): 
     return avg 
    elif (list[avg] < target): 
     return search(list[avg+1:], target) 
    else: 
     return search(list[:avg-1], target) 

    print "The location of the number in the array is", avg 

# The command line argument will create a list of strings        
# This list cannot be used for numeric comparisions          
# This list has to be converted into a list of ints          
def main(): 

    number = input("Please enter a number you want to search in the array !") 
    index = int(number) 
    list = [] 
    for x in sys.argv[1:]: 
    list.append(int(x)) 
    print "The list to search from", list 

    print(search(list, index)) 

if __name__ == '__main__': 
    main() 

CL : 
Anuvrats-MacBook-Air:Python anuvrattiku$ python binary_search.py 1 3 4 6 8 9 12 14 16 17 27 33 45 51 53 63 69 70 
Please enter a number you want to search in the array !69 
The list to search from [1, 3, 4, 6, 8, 9, 12, 14, 16, 17, 27, 33, 45, 51, 53, 63, 69, 70] 
0 
Anuvrats-MacBook-Air:Python anuvrattiku$ 

Answer 1

あなたのコードにはいくつか間違いがあります。それらを見つけるには、デバッガを使うか、トレースを追加して何が起こるのかを理解する必要があります。ここで問題自明作るトレースを使用して、元のコードは次のとおりです。

def search(list, target): 
    min = 0 
    max = len(list)-1 
    avg = (min+max)/2 
    print list, target, avg 
    ... 

あなたはすぐにそれを見ることができます：

• あなたは
平均以下であるときは、 avg-1をスキップサブアレイ内を検索します
• あなたはサブアレイで検索すると、あなたはその部分配列内のインデックスを取得します

の

修正は今些細です：

elif (list[avg] < target): 
     return avg + 1 + search(list[avg+1:], target) # add the offset 
    else: 
     return search(list[:avg], target) # sublist ends below the upper limit 

すべてではありません、あなたがmin == maxでループを終了するとき、あなたは（あなたがNoneを返すという意味）何も返しません。最後に、は決してという名前で、独自の変数として標準のPythonライブラリの名前を使用します。あなたはバイナリ検索が動作するようにソートされた配列/リストが必要であることを、知っています

def search(lst, target): 
    min = 0 
    max = len(lst)-1 
    avg = (min+max)/2 
    # uncomment next line for traces 
    # print lst, target, avg 
    while (min < max): 
    if (lst[avg] == target): 
     return avg 
    elif (lst[avg] < target): 
     return avg + 1 + search(lst[avg+1:], target) 
    else: 
     return search(lst[:avg], target) 

    # avg may be a partial offset so no need to print it here 
    # print "The location of the number in the array is", avg 
    return avg 

Answer 2

Python2とのpython3では、bisectを使用することができます。また、以下の

from bisect import bisect_left 

def search(alist, item): 
    'Locate the leftmost value exactly equal to item' 
    i = bisect_left(alist, item) 
    if i != len(alist) and alist[i] == item: 
     return i 
    raise ValueError 

alist = [1,2,7,8,234,5,9,45,65,34,23,12] 
x = 5 
alist.sort() # bisect only works on sorted lists 
print(index(a, x)) # prints 2 as 5 is on position 2 in the sorted list 

て検索してください置き換え 、AS SortedCollection (Python recipe)は役に立つかもしれません。

次のコード（from here）は、バイナリ検索を実行し、そのアイテムが見つかった場合は、位置を返します。上記の例で使用した場合

def binarySearch(alist, item): 
    first = 0 
    last = len(alist)-1 
    found = False 

    while first<=last and not found: 
     pos = 0 
     midpoint = (first + last)//2 
     if alist[midpoint] == item: 
      pos = midpoint 
      found = True 
     else: 
      if item < alist[midpoint]: 
       last = midpoint-1 
      else: 
       first = midpoint+1 
    return (pos, found) 

(2, True)を返します。

Answer 3

正しい結果が得られない理由は、すべての再帰呼び出しでコードがスライスされた配列を送信しているからです。配列の長さは減少し続けます。理想的には、元の配列を送信し、開始、終了インデックスのみを使用する方法を検討する必要があります。