プログラミング論 バイナリーサーチ http://www.ns.kogakuin.ac.jp/~ct13140/Prog/ 1

概要 アルゴリズム，計算量，オーダー 抽象的で，多少難しい． バイナリーサーチ 中程度． 2

アルゴリズム 問題を解決するための手法，手続き．処理を並べた手順． 必ず有限時間，有限の計算量で解けなくてはならない． 各手続きの意味が明瞭で無くてはならない． 主に計算機科学の分野で用いる 3

アルゴリズム 例えば 「複数の数字を大きい順に並び変える」 という問題があり， それを解決できる手法があったら,それがアルゴリズム． 4

アルゴリズの善し悪し アルゴリズの善し悪し 短時間，少ない処理数で問題を解決できるのが良いアルゴリズム 少ないメモリ消費で問題を解決できるのが良いアルゴリズム． プログラミングが楽なアルゴリズムが優れたアルゴリズム 5

計算量,計算時間 通常，問題の大きさが増すと，計算量や計算時間も増える． 「n個の整数の合計を求める」問題を解くのにかかる時間，計算量は「nに比例」． nが増えると，解くのにかかる時間も増える． 「1辺の長さがnの正方形型に列んだ整数の合計を求める」問題を解くのにかかる時間，計算量は「n2に比例」． 6

計算量のオーダー 計算量のオーダーは「おおよその計算量」 通常，一番支配的な(重要な)部分のみを語る． 計算量が(厳密には)「n2+2n+1」に比例するとき，「n2に比例する」と言い， O(n2)と表記し，「オーダーn2」と読む． 7

計算量のオーダー 基本的にnは巨大な数字を想定． 比例なので「3n2に比例」の様な考え方はない． そもそも計算量に単位はない． 計算量の単位が明確に分かり，例えば「比較回数がn3と10n3」の2種類があっても，共にO(n3)． 10倍の差は誤差として無視． 計算量が「1000n2」と「n3」では，前者がO(n2)，後者がO(n3)となり，前者の方が計算量が少ないと考える． 1000倍は無視．nが巨大なら事実．nが小さいなら計算量の考察は不要か，オーダーでは考えない． 8

アルゴリズムと計算量オーダー 同じ問題を解くアルゴリズムでも，計算量のオーダーが異なることがある． バケツソートはO(n)，Quick Sortは通常O(nlog(n))，バブルソートはO(n2)． nが大きい場合は，アルゴリズムにより計算時間が100倍や10000倍異なることは珍しくない． 9

大きい順/小さい順に並んでいる 配列の中から，目的の値を探す． バイナリーサーチ 二分探索 大きい順/小さい順に並んでいる 配列の中から，目的の値を探す． 10

ソートされたデータからの検索 ソートされた配列から，目的の数値を探す問題を考える． 次スライド以降でアルゴリズムを2個紹介 例えば，int a[100]に，100個の整数が入っており，それは昇順にソートされているとする． 何番目に，123が入ってるか(あるいは123はどこにも無いか)知るには？ 次スライド以降でアルゴリズムを2個紹介 11

単純な検索 0/3 a[0]が123か調査． a[1]が123か調査． a[2]が123か調査． (以下略) そうなら終了．そうで無ければ続ける． a[1]が123か調査． a[2]が123か調査． (以下略) 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を探す例． 13

単純な検索 2/3 データがn個あった場合， 運が良ければ1回の調査で見つかる． 運が悪ければ，n回の調査． 目的の数値が最初の1個だったとき． 運が悪ければ，n回の調査． 目的の数値が最後の1個だったとき． 平均すると，n/2回で見つかると期待される． よって，O(n)． オーダーを語るときは，O(n/2)とは言わない． 14

バイナリサーチ データがソートされていることを利用し，探索範囲を半減させていき，目的の値を発見するアルゴリズム． 2分法に非常に近い． 15

バイナリサーチ 以下を繰り返し，探索範囲を高速に狭めていく． 検索対象値が，L番目とR番目の間にあるとき， 検索対象は，(L+R)/2+1番目～R番目にある． 検索対象＜(L+R)/2番目の要素 なら， 検索対象は，L番目～(L+R)/2-1番目にある． 検索対象=(L+R)/2番目の要素 なら発見，終了． 16

バイナリサーチの例 a[10]の中から，55を検索． 以下の様になっており，a[6]が正解の例を考える． 10 21 31 32 46 48 67 69 77 17

バイナリサーチの例 a[10]の中から，55を検索． 調査前 L=0,R=9 検索対象はa[0]～a[9]にある． (0と9の中間は4.5だが，切り捨てする．切り上げでもよい) a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] ? ? ? ? 46 ? ? ? ? ? 調査後 L=5,R=9 検索対象は この範囲にある 18

バイナリサーチの例 a[10]の中から，55を検索． 調査前 L=5,R=9 検索対象はa[5]～a[9]にある． ? ? ? ? 46 ? ? 67 ? ? 調査後 L=5,R=6 検索対象は この範囲にある 19

バイナリサーチの例 a[10]の中から，55を検索． 調査前 L=5,R=6 検索対象はa[5]～a[6]にある． (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] ? ? ? ? 46 48 ? 67 ? ? 調査後 L=6,R=6 検索対象は この範囲にある 20

バイナリサーチの例 a[10]の中から，55を検索． 調査前 L=6,R=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 ? ? 検索対象は この範囲にある 21

バイナリサーチの例 a[10]の中から，55を検索． 調査前 L=6,R=6 検索対象はa[6]～a[6]にある． (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] ? ? ? ? 46 48 54 67 ? ? 調査後 L=7,R=6 検索対象は この範囲にある 22

while( left <= right ){ mid = (left + right)/2; 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; } 23

バイナリサーチ 検索時間はO(log(n))． 値の大小関係を利用しているので，ソートされていないデータには使用できない． 1回の調査で，データの検索範囲は半減する． 最悪でも，検索範囲のn個が，1になるまで繰り返せばよい．(途中で偶然見つかることもある) nは，何回半減させると1(以下)になるか？ → log2(n)回． 値の大小関係を利用しているので，ソートされていないデータには使用できない． 24

補足 通常のプログラミング言語では，ソートや検索のような基本的な機能は標準で提供されている． ソートの場合 検索では， C言語では，qsort()関数がある． Java,Ruby,Perlなどにもある．RDBMSにソート機能が用意されている． 検索では， Java,Ruby,Perlなどには，Hashがある． Hashは，O(1)で検索できる手法． 25

課題 a[0]～a[10]が 1,2,3,5,6,8,9,10,12,14,16 であり， これらの中から 9 を探すことを考える. L=0, R=10からはじめ， L,R,midの推移を記せ.