二分検索の2つの実装方法(再帰と非再帰)--python実装
1139 ワード
二分検索は私が初めて面接したときのプログラミング問題です.
再帰的でない方法:
個人的には覚えておきたい点:まず検索範囲があるので、low<=highでなければなりません.この範囲を超えると、検索する数が存在しないことを示すと、Noneに戻る.
次に、二分検索は検索範囲を縮小することであり、lowとhighを絶えず変更する方法である.
最後に、python構文について説明します.pythonには2つの除算があります.1つ目は正確な除算で、「/」という除算の結果は浮動小数点タイプの数に違いありません.2つ目は床除と呼ばれ、「//」これは実は整頓です.
再帰方式:
再帰方式は前述の通り、検索範囲があれば検索し、範囲がなければ見つからないことを示し、Noneに戻る.
再帰的でない方法:
#
def binary_search(list, item):
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high)//2
guess = list[mid]
if guess == item :
return mid
if item > guess :
low = mid + 1
else:
high = mid -1
return None
#
my_list = [1,3,4,5,6,7,8,9]
print(binary_search(my_list, 5))
print(binary_search(my_list, 2))
個人的には覚えておきたい点:まず検索範囲があるので、low<=highでなければなりません.この範囲を超えると、検索する数が存在しないことを示すと、Noneに戻る.
次に、二分検索は検索範囲を縮小することであり、lowとhighを絶えず変更する方法である.
最後に、python構文について説明します.pythonには2つの除算があります.1つ目は正確な除算で、「/」という除算の結果は浮動小数点タイプの数に違いありません.2つ目は床除と呼ばれ、「//」これは実は整頓です.
再帰方式:
#
def binary_s(list, low, high, item):
if low <= high:
mid = (low + high) //2
guess = list[mid]
if item == guess:
return mid
if item < guess:
binary_s(list, low, mid-1, item)
else:
binary_s(list, mid+1, high, item)
return None
#
my_list = [1,3,4,5,6,7,8,9]
print(binary_s(my_list, 0, len(my_list)-1, 5))
print(binary_s(my_list, 0, len(my_list)-1, 2))
再帰方式は前述の通り、検索範囲があれば検索し、範囲がなければ見つからないことを示し、Noneに戻る.