アルゴリズムを体で覚えてみる 二分探索

最近訳あってアルゴリズムの勉強をしてます。

いままであんまりアルゴリズムに強い関心を持ってたわけじゃないですし、
正直アルゴリズムなんて知らなくても大概のプログラムは書けると思うのですが・・・
やはりアルゴリズムは強力だなと思う今日このごろです。

超有名ですが、『二分探索』って改めてすごいなーと思ったので、
二分探索について書いてみたいと思います。

線形探索(配列の先頭から順番に調べてくあれです)と
二分探索の計算のオーダーをそれぞれ比較してみると・・・

* 線形探索 O(n)
* 二分探索 O(log n)

なのはたぶん有名だと思うのですが、
正直この凄さをあまり真面目に考えたことがなかったです。
ほんとプログラマーやっててすみませんでした。

なにがすごいって、、、
n=1,000,000の場合、
線形探索の場合、平均して500,000回の比較が必要となりますが、
二分探索の場合、最悪でもおよそ19回の比較で十分なんですよ。
いやほんとすみません・・・

ちょっとPythonで書いてみます。(バグってたらすみません)

def binsearch_rec(target, arr, l, r): 
    """ 再帰で二分探索をする関数

    target: 見つけ出したい値
    arr: targetを探索する配列
    l: arrの探索範囲の左端
    r: arrの探索範囲の右端

    前提条件: arrは昇順にソートされている必要がある
    戻り値： targetの見つかった位置。見つからなかった場合は-1
    """

    if l > r:
        # 探しに探したが見つからなかった
        return -1

    m = (l + r) / 2 # 探索範囲の真ん中のindexを計算
    if target < arr[m]:
        # 見つけたい値がarrの真ん中より小さかったら
        # mより左の範囲を再帰的に探す。
        return binsearch_rec(target, arr, l, m-1)
    elif target > arr[m]:
        # 見つけたい値がarrの真ん中より大きかったら
        # mより右の範囲を再帰的に探す。
        return binsearch_rec(target, arr, m+1, r)
    else:
        # 見つけた！
        return m

↑は再帰バージョンですが、ループを使う方法もあります。

def binsearch_loop(target, arr):
    l = 0 
    r = len(arr)-1
    while l <= r:
        m = (l + r) / 2 
        if target < arr[m]:
            r = m-1 
        elif target > arr[m]:
            l = m+1
        else:
            return m
    return -1

趣味だとは思いますが、個人的には再帰を使う方が覚えやすいです。
ですが、ループのほうが関数の呼び出し分のロスがない分、
速いという噂もあります。



正直なところ、探索が必要なときは
今まですべて線形探索してました。
というか二分探索する必要すらなかったのですが・・・
・・・にしても自己嫌悪に陥いりますわ。