LoginSignup
2
2

More than 5 years have passed since last update.

Pythonによる二分探索法

Posted at

初めまして。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だと思いますが、どうでしょうか。皆様のご意見を伺いたいです。

2
2
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
2