初めまして。python初学者の初投稿です。
コードを書いてみた、、が
binary_research.py
def binary_search(numbers, target):
#中央値(切り捨て)=center
center = len(numbers)//2
#長さが変わった後のリストの1番目が本来の何番目の数か−1=index
index = 0
while numbers[center-1] != target:
#中央値よりターゲットが大きいとき中央値以下をリストから消しindexを更新
if numbers[center-1] < target:
numbers = numbers[center:]
index = index + center
#中央値よりターゲットが小さいとき中央値より大きい部分をリストから消す
else:
numbers = numbers[:center]
#次の中央値計算
center = len(numbers)//2
#centerが切り捨てにの影響で0になってしまうことを防ぐ
if center == 0:
center = 1
print(str(target)+"は"+str(index+center)+"番目にあります")
#実行例
numbers = [1, 2, 4, 8, 9, 11, 12, 15, 17, 20, 21, 24, 30]
target = 9
binary_search(numbers, target)
と拙い頭で「中央値の判定により、listから半分削除して探索していく」という方針でコードを書いてみましたが、先人のコードを検索するとどうやら「中央値判定により、探索する必要のない側の半分から端の値を削っていく」というのが主流(というか正解?)らしくて肩を落としてます。
いずれのコードでもn個の数字に対する計算量のオーダーはlognだと思いますが、どうでしょうか。皆様のご意見を伺いたいです。