二分探索

昨日の続きで二分探索。
こいつも相当簡単な探索。

探索対象(リスト)のある位置x(大概は真ん中)を見て、探したいものがxより大きければその後ろを、小さければその前を、といった具合に探索範囲を狭めながら探索をおこなっていく。
ただし、前提条件としてソートが完了しているものにしか対応しない。
ソートができていないと探索自体が破綻する。
なので線形探索より高速だが使える場面は限定される。

実装してみる。
ついでに線形探索との探索時間の比較をしてみた。
Pythonでの時間の測り方はまだよく分かっていないので今回使った方法が正しいのかは若干疑問。
またtimeitについて↓のあたりで調べておく。
http://morchin.sakura.ne.jp/effective_python/timeit.html

それでは実験。

def Search(target, numList):
    for x in numList:
        if x == target:
            return True
    return False

def Search2(target, numList):
    min_pos = 0
    max_pos = len(numList) - 1

    while min_pos <= max_pos:
        mid_pos = (min_pos + max_pos) / 2

        if target == numList[mid_pos]:
            return True
        elif target > numList[mid_pos]:
            min_pos = mid_pos + 1
        else: # target < numList[mind_pos]
            max_pos = mid_pos - 1
    return False


if __name__ == "__main__":
    import time

    numList = [x for x in range(100000)]

    start = time.clock()
    Search(100, numList)
    print time.clock() - start

    start = time.clock()
    Search2(100, numList)
    print time.clock() - start
    print 

    start = time.clock()
    Search(90000, numList)
    print time.clock() - start

    start = time.clock()
    Search2(9000, numList)
    print time.clock() - start

そして実行結果がこちら

C:\practice\Python\2-16>Python search2.py
2.34666696466e-005
3.10095277472e-005

0.00703776597305
2.82158765988e-005

線形探索はリストの前半に探索対象がある時は割りと高速。
しかし、リストの後半だと探索時間のオーダーが変わってくる。

探索回数がリストの要素数をとしたときに
線形探索
(平均してリストの大きさ分の探索が必要)
に対して
二分探索

だったけかな。

これで上の実験結果の辻褄もあうね。