pythonを用いてリストの二分検索をループと再帰で実現する
1466 ワード
二分検索パラメータの解釈とクエリーの原理:
二分検索の前提はリストの順序です.次に、昇順リストを例に挙げます.order_Listはシーケンステーブルがあり、keyは検索が必要な値であり、leftとrightはリストまたは配列の中で左右の下付き文字に相当し、配列またはリストの[left,right]範囲内で検索し、検索中に[left,right]がカバーする範囲を縮小し続け、検索が成功するまで下付き文字を返し、Noneに戻ることができないことを示す.サイクルおよび再帰的実装を以下に示す.
循環による二分検索:
再帰的に二分検索を実現する:
二分検索の前提はリストの順序です.次に、昇順リストを例に挙げます.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)