エスキュービズム ラボ Blog

今回は、二分探索法について解説します。

1.逐次探索

通常、n個の配列(list)の中からある要素(target)を調べる場合、次のようにします。


for i in range(len(list)):
 if i == target:
    return i
return -1   #false

これは逐次探索と 呼ばれます。(線形探索とも呼ばれ

る。)

この方法は単純ですが一般に、データ量に比例して作業量も増えてしまいます。

2.二分探索

二分探索の簡単な例を下に示します。

これは1から100の間の整数を30個持つリスト

から、ある数字（ここでは60)を見つける二分検索の様子を表したものです。
逐次検索であれば、20個目を見るまで発見できない60が、たったの4回で発見されています。

一般にn個の要素からなるリストからある要素を検索する場合

逐次探索では、n/2回

二分探索法ではlog2(n)回

で発見することが出来ます。

y = log2(x)のグラフとy= x/2のグラフの比較

データ量が多い場合二分探索は圧倒的に効率的です。

3.考え方

基本的な考え方: tが配列x[1..n-1]内にあるなら、それは限定されたある範囲内(探索範囲内)にあるはずである。

二分探索は、tのあるべき範囲を限定していく探索方法

1回目:全体の中央値を調べる。

2回目:限定された範囲の中央値を調べる

3回目～同様の繰り返し

もし探索範囲が空になれば、要素は存在しない。

4.実際のコード

実際にPythonのコードを見てみましょう。

#!/usr/local/bin/python
# -*- encoding: utf-8 -*-

import math
import random
import datetime

def binary_search(target, numList):
    lower = 0
    upper = len(numList) - 1
    time = 0
    while lower <= upper:
        where = (lower + upper) / 2
        print “where = “ + str(where) + “: “,
        time += 1
        if target == numList[where]:
            print “発見しました:” + str(time) + “回目”
            return where
        elif target < numList[where]:
            print “continue”
            upper = where - 1
        else:
            print “continue”
            lower = where + 1
    print “発見できませんでした:” + str(time) + “回目”
    return -1

random.seed()
sampleList = [random.randint(1,20000) for i in range(10000)]
sampleList.sort()
random.seed()
target = random.randint(1,20000)
print str(target) + “を探します。”
print binary_search(target, sampleList)
 

<実行結果>

 

19919を探します。
where = 4999:  continue
where = 7499:  continue
where = 8749:  continue
where = 9374:  continue
where = 9687:  continue
where = 9843:  continue
where = 9921:  continue
where = 9960:  continue
where = 9940:  continue
where = 9950:  continue
where = 9955:  continue
where = 9957:  発見しました:12回目
9957

 

平均して、


import math

math.log(10000, 2)

で、13.2877123795回で見つかることが分かります。

 

8/22　追記

5.実際に逐次探索と二分探索法のパフォーマンスを比較してみました。

プログラムは上記のものを多少変え、以下のようなものを使用しました。

import math
import random

SAMPLE_LIST = [i+1 for i in range(20000)]

def binary_search1():
    target = random.randint(1,20000)
    lower = 0
    upper = len(numList) - 1
    while lower <= upper:
        where = (lower + upper) >> 1   #　変更部分
        a = SAMPLE_LIST[where]
        if target > a:        #　変更部分
            lower = where + 1
        elif target < a:
            upper = where - 1
        else:
            return where
    return -1

def binary_search2():
    target = random.randint(1,20000)
    lower = 0
    upper = len(SAMPLE_LIST) - 1
    while lower <= upper:
        where = (lower + upper) / 2
        if target == SAMPLE_LIST[where]:
            return where
        elif target < SAMPLE_LIST[where]:
            upper = where - 1
        else:
            lower = where + 1
    return -1

def search():
    target = random.randint(1,20000)
    for i in range(len(SAMPLE_LIST)):
        if i == target:
            return 1
    return -1

binary_search()の4で書いたプログラムとの相違点は、

(lower + upper) / 2 => (lower + upper) >> 1

としてシフト演算子を利用している点、及び

if文の順番を(等号、不等号、else）から(不等号、不等号、else)と変えている点です。（等号が起こる確率が低いので最後に移した。）

 

このプログラムそれぞれに対して、Pythonのtimeitモジュールを利用してパフォーマンスを計算したところ、以下の結果が分かりました。

1万回の実行にかかる平均時間：

binary_search:0.13559007287秒

search:21.7876970768秒

binary_searchのパフォーマンスはsearchの約160.688倍ということが分かりました。

(備考)

また、4に書いたプログラムを利用して同様のことをおこなったところ

4のbinary_search()に比べて、6のbinary_search()は115.5%程度のパフォーマンスを発揮することが分かりました。

さらに詳しく調べたところ、if文の変更による寄与が約７%、シフト演算子による寄与が約4%であることが分かりました。

 

参考文献:
珠玉のプログラミング：ジョン・ベントリー著 ピアソン・エデュケーション
プログラミング作法：Braian W.kernighan Rob Pike 福崎俊博 訳 株式会社ASCII