pythonを用いてリストの二分検索をループと再帰で実現する


二分検索パラメータの解釈とクエリーの原理:
二分検索の前提はリストの順序です.次に、昇順リストを例に挙げます.order_Listはシーケンステーブルがあり、keyは検索が必要な値であり、leftとrightはリストまたは配列の中で左右の下付き文字に相当し、配列またはリストの[left,right]範囲内で検索し、検索中に[left,right]がカバーする範囲を縮小し続け、検索が成功するまで下付き文字を返し、Noneに戻ることができないことを示す.サイクルおよび再帰的実装を以下に示す.
循環による二分検索:
#          
a = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69, 107]
user_input = int(input("         :"))

def while_half_search(order_list, key, left, right):
    while left <= right:
        mid = (left + right)  #               
        if key > order_list[mid]:
            left = mid + 1
        elif key < order_list[mid]:
            right = mid - 1
        else:
            return mid
    return None


left = 0
right = len(a) - 1
result = while_half_search(a, user_input, left, right)
print(result)

再帰的に二分検索を実現する:
#      2      
a = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69, 107]
# print(len(a))

user_input = int(input("         :"))

def HalfSearch(OrderedList, key, left, right):
    if left > right:
        return None
    mid = (left + right) // 2
    if key == OrderedList[mid]:
        return mid
    elif key > OrderedList[mid]:
        return HalfSearch(OrderedList, key, mid + 1, right)
    else:
        return HalfSearch(OrderedList, key, left, mid - 1)


left = 0
right = len(a) - 1
index = HalfSearch(a, user_input, left, right)
print(index)