再帰（Recursion）について既に２個ほど記事を書きましたが、今回は再帰を使って二分探索（Binary Search）のコードを書いていこうかなと思います。
再帰とは何かを知りたい方向け。
再帰の実践的な使い方を知りたい方向け。
二分探索（Binary Search）とは
二分探索の細かい定義などは良かったらwikipediaなどで確認してみてください。ここでは具体例だけ出すものとします。
こんな ソートされた リストを想定してください。
alist = [1, 2, 3, 4, 5, 6, 7, 8, 9]
このリストの中で３という要素が含まれているかどうかを調べたいとします。
このような時有効な方法の一つが二分探索です。
具体的にどのようなことをするかというと、リストの真ん中のインデックスの値のデータとターゲットを見比べることを繰り返すことでターゲットの存在しているであろう場所を絞り込んでいくということをします。
注 インデックスとは各データの場所のことで、リストの最初の値である1のインデックス0から右に行くごとに１ずつ増えて行きます。
この例でいうと全部で9つの値があるので真ん中のインデックス4のデータである５とターゲットの３を比べます。そうすると５の方が大きいので、6以降にターゲットが存在していないこととインデックスが4未満のデータにターゲットが存在していることが分かります。
なので次はインデックス０と４の間すなわちインデックス２のデータとターゲットの値である３を見比べます。今回インデックス２のデータがターゲットである３なのでここで探索は終了します。（もしインデックス２が３でなければまた大小の比較が行われてターゲットの範囲が絞られて行きます。）
データの大小関係でターゲットの範囲が絞り込まれて行くので、リストの中身が小から大あるいは小から大など比較できるように並び替えられていることが二分探索の使える 条件となります。
どんなアルゴリズムなのか
まずリストの真ん中に当たるmidpointを定義する。
注 リストは再帰の時に範囲を狭めて行くので、真ん中のインデックスも再帰するたびに変わってきます。
ベースケース
もしリストの範囲を絞っていった結果ターゲットを見つけられず、最後にからのリストになった場合はFalseを返す。
もしリストにターゲットが含まれておりインデックスがmidpointでターゲットを見つけた場合Trueを返す。
再帰
・ケース１
もしターゲットがmidpointのデータより小さい時
midpointより大きい部分のリストを捨てて再帰します。
・ケース２
もしターゲットがmidpointのデータより大きい時
midpointより小さい部分のリストを捨てて再帰します。
実際のコードは
def binarysearch(somelist, target):
if somelist == :
print(somelist)
return False
else:
print(somelist)
midpoint = len(somelist) // 2
print("midpoint:", midpoint)
if target == somelist[midpoint]:
return True
elif target < somelist[midpoint]:
return binarysearch(somelist[:midpoint],target)
else: # target > somelist[midpoint] の時
return binarysearch(somelist[midpoint+1:],target)
alist = [1,2,3,4,5,6,7,8,9]
#関数を呼び出してみる
boolean = binarysearch(alist,3)
print(boolean)
boolean = binarysearch(alist,6)
print(boolean)
boolean = binarysearch(alist,12)
print(boolean)
実行結果
ターゲット ３
[1, 2, 3, 4, 5, 6, 7, 8, 9]
midpoint: 4
[1, 2, 3, 4]
midpoint: 2
True
ターゲット ６
[1, 2, 3, 4, 5, 6, 7, 8, 9]
midpoint: 4
[6, 7, 8, 9]
midpoint: 2
[6, 7]
midpoint: 1
[6]
midpoint: 0
True
ターゲット １２
[1, 2, 3, 4, 5, 6, 7, 8, 9]
midpoint: 4
[6, 7, 8, 9]
midpoint: 2
[9]
midpoint: 0
False
>>>
このように少しずつ範囲が狭まっていき、最終的にターゲットが見つかってTrueを返すとか、見つからずにFalseを返しているのが確認できると思います。
ちなみに、
最後の12を探す途中、リストは[9]を返しています。この場合elseの枝先のreturn binarysearch(somelist[midpoint+1:],target)が実行されるんですけど、もし要素が一つしかない状態でそれより大きいインデックス以上のリストのスライスをする場合、空のリストがreturnで返されます。
良かったら自分で試してみてください。
時間計算量（Time Complexity）
時間計算量（Time Complexity）はLog2N (底は２)
毎回の操作で、リストの数が２分割にされていることから、線形探索法（Sequential Search ループで一個ずつ要素をチェックする方法）の時間計算量であるNより早くみつかる、すなわっちNより小さい値であることは予想ができるかなと思います。
ここまで読んでいただきありがとうございました。
もし理論や技術的な間違いがあった場合お知らせしていただけると助かります。
打ち間違いなどに関しましては後々自分の方で治していこうと思っています。
