プログラミング論 II
2010年07月08日
バイナリーサーチ
http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2010/
J-1
概要
• アルゴリズム，計算量，オーダー
– 抽象的で，多少難しい．
• バイナリーサーチ
– 中程度．
J-2
アルゴリズム
• 問題を解決するための手法，手続き．処理を並
べた手順．
– 必ず有限時間，有限の計算量で解けなくてはならな
い．
– 各手続きの意味が明瞭で無くてはならない．
– 主に計算機科学の分野で用いる
J-3
アルゴリズム
• 例えば
「複数の数字を大きい順に並び変える」
という問題があり，
それを解決できる手法があったら,それがアルゴ
リズム．
J-4
アルゴリズの善し悪し
• アルゴリズの善し悪し
– 短時間，少ない処理数で問題を解決できるのが良い
アルゴリズム
– 少ないメモリ消費で問題を解決できるのが良いアルゴ
リズム．
– プログラミングが楽なアルゴリズムが優れたアルゴリ
ズム
J-5
計算量,計算時間
• 通常，問題の大きさが増すと，計算量や計算時
間も増える．
– 「n個の整数の合計を求める」問題を解くのにかかる
時間，計算量は「nに比例」．
• nが増えると，解くのにかかる時間も増える．
– 「1辺の長さがnの正方形型に列んだ整数の合計を求
める」問題を解くのにかかる時間，計算量は「n2に比
例」．
J-6
計算量のオーダー
• 計算量のオーダーは「おおよその計算量」
• 通常，一番支配的な(重要な)部分のみを語る．
– 計算量が(厳密には)「n2+2n+1」に比例するとき，
「n2に比例する」と言い，
O(n2)と表記し，「オーダーn2」と読む．
J-7
計算量のオーダー
• 基本的にnは巨大な数字を想定．
• 比例なので「3n2に比例」の様な考え方はない．
– そもそも計算量に単位はない．
– 計算量の単位が明確に分かり，例えば「比較回数が
n3と10n3」の2種類があっても，共にO(n3)．
• 10倍の差は誤差として無視．
• 計算量が「1000n2」と「n3」では，前者がO(n2)，
後者がO(n3)となり，前者の方が計算量が少な
いと考える．
– 1000倍は無視．nが巨大なら事実．nが小さいなら計
算量の考察は不要か，オーダーでは考えない．
J-8
アルゴリズムと計算量オーダー
• 同じ問題を解くアルゴリズムでも，計算量のオー
ダーが異なることがある．
– バケツソートはO(n)，Quick Sortは通常
O(nlog(n))，バブルソートはO(n2)．
– nが大きい場合は，アルゴリズムにより計算時間が
100倍や10000倍異なることは珍しくない．
J-9
バイナリーサーチ
二分探索
大きい順/小さい順に並んでいる
配列の中から，目的の値を探す．
J-10
ソートされたデータからの検索
• ソートされた配列から，目的の数値を探す問題を
考える．
– 例えば，int a[100]に，100個の整数が入ってお
り，それは昇順にソートされているとする．
何番目に，123が入ってるか(あるいは123はどこに
も無いか)知るには？
• 次スライド以降でアルゴリズムを2個紹介
J-11
単純な検索 0/3
• a[0]が123か調査．
– そうなら終了．そうで無ければ続ける．
• a[1]が123か調査．
• a[2]が123か調査．
(以下略)
J-12
単純な検索 1/3
for(i=0; i<100; i++){
if( a[i] == 123 ){
printf(“a[%d]が123.\n",i);
break;
}
}
int a[100]の中から，
(つまりa[0]～a[99]の中から)
123を探す例．
J-13
単純な検索 2/3
• データがn個あった場合，
– 運が良ければ1回の調査で見つかる．
• 目的の数値が最初の1個だったとき．
運が悪ければ，n回の調査．
• 目的の数値が最後の1個だったとき．
– 平均すると，n/2回で見つかると期待される．
• よって，O(n)．
• オーダーを語るときは，O(n/2)とは言わない．
J-14
バイナリサーチ
• データがソートされていることを利用し，探索範囲
を半減させていき，目的の値を発見するアルゴリ
ズム．
• 2分法に非常に近い．
J-15
バイナリサーチ
• 以下を繰り返し，探索範囲を高速に狭めていく．
• 検索対象値が，L番目とR番目の間にあるとき，
(L+R)/2番目の要素に注目し，
「(L+R)/2番目の要素」と「検索対象」を比較．
– (L+R)/2番目の要素＜検索対象 なら，
検索対象は，(L+R)/2+1番目～R番目にある．
– 検索対象＜(L+R)/2番目の要素 なら，
検索対象は，L番目～(L+R)/2-1番目にある．
– 検索対象=(L+R)/2番目の要素 なら発見，終了．
J-16
バイナリサーチの例
• a[10]の中から，55を検索．
– 以下の様になっており，a[6]が正解の例を考える．
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
10
21
31
32
46
48
55
67
69
77
J-17
バイナリサーチの例
調査前
L=0,R=9
• a[10]の中から，55を検索．
– 検索対象はa[0]～a[9]にある．
中間のa[4]を調査し，検索対象と大小比較をしてみる．
「a[4]＜検索対象」なので，
検索対象は，a[4]よりも右にあることが分かる．
(0と9の中間は4.5だが，切り捨てする．切り上げでもよい)
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
?
調査後
L=5,R=9
?
?
?
46
?
?
?
?
検索対象は
この範囲にある
?
J-18
バイナリサーチの例
調査前
L=5,R=9
• a[10]の中から，55を検索．
– 検索対象はa[5]～a[9]にある．
中間のa[7]を調査し，検索対象と大小比較をしてみる．
「検索対象＜a[7]」なので，
検索対象は，a[7]よりも左にあることが分かる．
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
?
調査後
L=5,R=6
?
?
?
46
?
?
67
検索対象は
この範囲にある
?
?
J-19
バイナリサーチの例
調査前
L=5,R=6
• a[10]の中から，55を検索．
– 検索対象はa[5]～a[6]にある．
中間のa[5]を調査し，検索対象と大小比較をしてみる．
(5と6の中間は5.5であり,切り捨てで5とした)
「a[5]＜検索対象」なので，
検索対象は，a[5]よりも右にあることが分かる．
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
?
調査後
L=6,R=6
?
?
?
46
48
?
67
検索対象は
この範囲にある
?
?
J-20
バイナリサーチの例
調査前
L=6,R=6
• a[10]の中から，55を検索．
– 検索対象はa[6]～a[6]にある．
中間のa[6]を調査し，検索対象と大小比較をしてみる．
(6と6の中間は6としましょう...)
「a[6]=検索対象」なので，検索終了．
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
?
?
?
?
46
48
55
67
検索対象は
この範囲にある
?
?
J-21
バイナリサーチの例
調査前
L=6,R=6
• a[10]の中から，55を検索．
– 検索対象はa[6]～a[6]にある．
中間のa[5]を調査し，検索対象と大小比較をしてみる．
(6と6の中間は6としましょう...)
もし，「a[6]＜検索対象」だったら，Lは7となる．
L＞Rとなってしまったら，「存在しない」で終了．
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
?
調査後
L=7,R=6
?
?
?
46
48
54
67
検索対象は
この範囲にある
?
?
J-22
left = 0;
right = SIZE-1;
while( left <= right ){
mid = (left + right)/2;
if( data[mid] == target ){
target_index = mid;
break;
} else if( data[mid] < target ){
left = mid+1;
} else if( target < data[mid] ){
right = mid-1;
}
}
J-23
バイナリサーチ
• 検索時間はO(log(n))．
– 1回の調査で，データの検索範囲は半減する．
– 最悪でも，検索範囲のn個が，1になるまで繰り返せ
ばよい．(途中で偶然見つかることもある)
– nは，何回半減させると1(以下)になるか？
→ log2(n)回．
• 値の大小関係を利用しているので，ソートされて
いないデータには使用できない．
J-24
補足
• 通常のプログラミング言語では，ソートや検索の
ような基本的な機能は標準で提供されている．
• ソートの場合
– C言語では，qsort()関数がある．
– Java,Ruby,Perlなどにもある．RDBMSにソート機
能が用意されている．
• 検索では，
– Java,Ruby,Perlなどには，Hashがある．
– Hashは，O(1)で検索できる手法．
J-25
課題
• a[0]～a[10]が
1,2,3,5,6,8,9,10,12,14,16 であり，
これらの中から 9 を探すことを考える.
L=0, R=10からはじめ，
L,R,midの推移を記せ.
J-26
© Copyright 2024 ExpyDoc
