うちぱらららららr

プログラミングやその周辺のことを主に書きます。

二分探索 ~hogehoge~

ほ GE 

新年あけましておめでとうございます().

新年初の記事です.

いつの間にか年が明けたと思ったら,新学期が始まっていました.かなしいですね.まあ,頑張っていきましょう.

今年は,文章力や語彙力などを上げるためになるべく記事を書いていこうと思います.

ぽよ

ふとアルゴリズムとデータ構造を勉強したいなとおもったのでいい感じに書いていこうと思います.なるべく続けていくぞ~~.

二分探索ってなんやねん

二分探索とは…

https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2

らしいです.

Sort済みの配列を半分にして真ん中の値をとり,探したい値より小さいか大きいかを判定してうぇ~~~ってしてそこからまた繰り返すみたいな感じですね.

実装

Python3で実装してみます.

def binary_search(list1, search):
    '''
    探索して見つかった場合は配列の番号を返し,
    見つからない場合はNoneを返す.
    '''
    low = 0
    high = len(list1) - 1

    while low <= high:
        mid = (low + high) // 2  #中央の値

        if search == list1[mid]: # 一致した場合
            return mid
        if search > list1[mid]: # 小さかった場合
            low = mid + 1
        else:                   # 大きかった場合
            high = mid - 1

    return None            # なかった場合

def main():
    print(binary_search(list(range(20)), 3))  #0~19の中に3があるか
    print(binary_search(list(range(20)), -1)) #0~19の中に-1があるか

if __name__ == '__main__':
    main()

わかりにくい場合は図をかきながらやってみるといいかもしれないです.

おわり

解説のはwikipediaに丸投げですね.
文章でいい感じに説明できるようになりたいです ><.

変なところやくそっぽいところがあったら教えてくれるとうれしいです><