【Python】【アルゴリズム】二分探索法(バイナリサーチ)
- 作者: 伊藤静香
- 出版社/メーカー: インプレス
- 発売日: 2016/03/16
- メディア: Kindle版
- この商品を含むブログ (1件) を見る
息抜きにアルゴリズムの勉強を始めました。
「アルゴリズムを、はじめよう」では、以下のアルゴリズムをフローチャートと擬似言語を使って噛み砕いて説明してくれます。
- 線形探索法(リニアサーチ)
- 二分探索法(バイナリサーチ)
- ハッシュ探索法
- 単純交換法(バブルソート)
- クイックソート
- エラトステネスのふるい
- ユークリッドの互除法
- 単純選択法(選択ソート)
- 単純挿入法(挿入ソート)
実際のプログラミング言語を用いた説明はないので、Pythonで実装しながら読み進めていこうと思います。
線形探索法(リニアサーチ)
- 0~9までの整数が昇順で並んだリストから、引数で指定された整数をリニアサーチします。
linear_search.py
import sys ls = list(range(0,10)) target = int(sys.argv[1]) for x in ls: if(x == target): print("I found ", target, "!", sep='') sys.exit() else: print(x) print("I couldn't find ", target, ".", sep='')
>python linear_search.py 8 0 1 2 3 4 5 6 7 I found 8! >py linear_search.py 11 0 1 2 3 4 5 6 7 8 9 I couldn't find 11.
二分探索法(バイナリサーチ)
binary_search.py
import sys ls = list(range(0,10)) head = 0 tail = len(ls)-1 target = int(sys.argv[1]) print("target:", target) while(head <= tail): print("head:", head) print("tail:", tail) print(ls[head:tail+1]) center = int((head+tail)/2) print("center:", center) if(ls[center] == target): print("I found ", target, "!", sep='') exit() elif ls[center] < target: head = center + 1 else: tail = center - 1 print() print("I couldn't find ", target, ".", sep='')
>python binary_search.py 5 target: 5 head: 0 tail: 9 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] center: 4 head: 5 tail: 9 [5, 6, 7, 8, 9] center: 7 head: 5 tail: 6 [5, 6] center: 5 I found 5!