0

二分探索の再帰バージョンの実装を作成しようとしています。これは私がこれまでに持っているものです。終了方法がわかりません。

def binarySearch(searchList, numberSought, low, high):
    if high < low:
        return False
    midpoint = (low + high)//2
    print ("high is index", high)
    print ("low is index", low)
    print ("midpoint is index", midpoint)
    if searchList[midpoint] == numberSought:
        return True
    elif ...

    else:
        ...

mylist = [2, 4, 7, 13, 21, 22, 27, 31, 41, 77, 97, 144, 168]
first = 0
last = len(mylist) - 1
candidate = int(input("Does our list contain the following number? "))
print ("It is ",binarySearch(mylist,candidate,first,last), "that our list contains", candidate)
4

3 に答える 3

0

この再帰プログラムを使用して、バイナリ検索を実行できます。

>>>def BS(list,key,min,max):
    if max<min:
        return None
    else:
        mid=(min+(max-min)/2)
    if list[mid]>key:
        return BS(list,keyey,min,mid-1)
    elif list[mid]<key:
        return BS(list,key,mid+1,max)
    else:
        return mid

>>> min = 0
>>> list = [2, 4, 7, 13, 21, 22, 27, 31, 41, 77, 97, 144, 168]
>>> max = len(list)-1
>>> key = 21
>>> BS(list,key,min,max)

ウィキによると: 二分探索または半区間探索アルゴリズムは、キー値でソートされた配列内で指定された入力値 (検索「キー」) の位置を見つけます。[1][2] 各ステップで、アルゴリズムは検索キー値を配列の中央要素のキー値と比較します。キーが一致する場合、一致する要素が見つかり、そのインデックスまたは位置が返されます。それ以外の場合、検索キーが中央の要素のキーよりも小さい場合、アルゴリズムは中央の要素の左側のサブ配列でアクションを繰り返します。検索キーが大きい場合は、右側のサブ配列でアクションを繰り返します。検索する残りの配列が空の場合、配列内でキーが見つからず、特別な「見つかりません」という指示が返されます。

于 2013-07-30T17:57:26.533 に答える