218. 二分探索
放送大学で取り上げられた二つ目の探索の方法がここで紹介する二分探索である。
数多くある配列の中から探す、とか近似値を算出する方法として
全体を二つに分割して小さいほうにあるのか、大きいほうにあるのか判断を
繰り返す手法である。
この理論は理解している人は多いはずであるが実際のソースとなると
具体的な記述が難しいというか、なかなか想像できない。
そこでここでは放送大学で放送されたソースを IBM System i でも
実行可能なソースに書き換えたものを紹介する。
【 サンプル・ソース：TESTBINS 】
0001.00 H DFTNAME(TESTBINS) DATEDIT(*YMD/) 0002.00 F********** TESTBINS: 二分探索 **************************************** 0003.00 F* 0004.00 F********************************************************************** 0005.00 D BIN_SEARCH PR 4S 0 0006.00 D AR 4S 0 VALUE DIM(10) 0007.00 D KEY 4S 0 VALUE 0008.00 D NUM 4S 0 VALUE 0009.00 0010.00 D AR S 4S 0 DIM(10) 0011.00 D TRUE S 4S 0 INZ(0) 0012.00 D FALSE S 4S 0 INZ(-1) 0013.00 D KEY S 4S 0 INZ(35) 0014.00 D RES S 4S 0 0015.00 D FLD4 S 4A 0016.00 D NUM S 4S 0 0017.00 0018.00 C '* TESTBINS *'DSPLY ANS 1 0019.00 C EVAL NUM = %ELEM(AR) 0020.00 C EVAL RES = BIN_SEARCH(AR:KEY:NUM) 0021.00 C IF RES = FALSE 0022.00 C '* NOT FOUND 'DSPLY ANS 0023.00 C ELSE 0024.00 C MOVE RES FLD4 0025.00 C DOW %SUBST(FLD4:1:1)= '0' 0026.00 C EVAL FLD4 = %SUBST(FLD4:2:3) 0027.00 C ENDDO 0028.00 C 'FOUND AT ' CAT FLD4 DSP40 40 0029.00 C DSP40 DSPLY ANS 0030.00 C ENDIF 0031.00 C SETON LR 0032.00 C RETURN 0033.00 C****************************************************** 0034.00 C *INZSR BEGSR 0035.00 C****************************************************** 0036.00 C Z-ADD 0 AR(1) 0037.00 C Z-ADD 5 AR(2) 0038.00 C Z-ADD 10 AR(3) 0039.00 C Z-ADD 15 AR(4) 0040.00 C Z-ADD 20 AR(5) 0041.00 C Z-ADD 25 AR(6) 0042.00 C Z-ADD 30 AR(7) 0043.00 C Z-ADD 35 AR(8) 0044.00 C Z-ADD 40 AR(9) 0045.00 C Z-ADD 45 AR(10) 0046.00 C ENDSR 0047.00 C****************************************************** 0048.00 P BIN_SEARCH B EXPORT 0049.00 C****************************************************** 0050.00 D PI 4S 0 0051.00 D AR 4S 0 VALUE DIM(10) 0052.00 D KEY 4S 0 VALUE 0053.00 D NUM 4S 0 VALUE 0054.00 D N S 4S 0 0055.00 D LOW S 4S 0 INZ(0) 0056.00 D HIGH S 4S 0 0057.00 D MIDDLE S 4S 0 0058.00 0059.00 C EVAL HIGH = NUM + 1 0060.00 C DOW LOW <= HIGH 0061.00 C EVAL MIDDLE = (LOW + HIGH)/2 0062.00 C IF KEY = AR(MIDDLE) 0063.00 C RETURN MIDDLE 0064.00 C ELSE 0065.00 C IF KEY <= AR(MIDDLE) 0066.00 C EVAL HIGH = MIDDLE - 1 0067.00 C ELSE 0068.00 C EVAL LOW = MIDDLE + 1 0069.00 C ENDIF 0070.00 C ENDIF 0071.00 C ENDDO 0072.00 C RETURN FALSE 0073.00 P E
【解説】
探索する配列の対象の範囲の最小の指標を LOW, 最大の指標を HIGH と定義している。
そこで LOW と HIGH のあいだの MIDDLE = (LOW + HIGH)/2 中間の指標の値 AR(MIDDLE) が
探索キー KEY と比較して 同じであれば、求める探索は見つかったであるから RETURN MIDDLE として
終了する。
KEY のほうが小さいのであれば HIGH を HIGH = MIDDLE - 1 として HIGH の値を置き換えることによって
探索の範囲を半分にする。
逆に KEY のほうが大きいのであれば LOW を LOW = MIDDLE + 1 として LOW の値を置き換えることによって
探索の範囲を繰り返す。
このようにして LOW と HIGH の範囲を徐々に狭くしていって最後に MIDDLE を見つけるものである。
DOWHILE 文をすべて繰り返しても見つからなかったのであれば、RETURN FALSE で戻す。
二分探索は線形探索に比べて無駄なくかなり速い処理となる。
例えば、100万個の配列を線形探索で探索してみると、見つかるまでの平均比較回数は 50万回であるのに
対して二分探索であれば約 20 回で見つけることができる。
(二分探索の比較回数は log2N として算出される。2 を底とする LOG (対数)は高校1年の教科書を
思い出して ! )
ただし、この二分法が使えるための前提となる条件は探索の対象となる配列が事前に昇順に分類( SORT )
されている必要がある。
とはいうものの二分探索の方法は単純に比較を繰り返す線形探索に比べて圧倒的に効率よいことが
これでわかる。
実は IBM System i の DB2/400 のキーによる検索も原則はこの方法によって検索されている。
読者が自分が開発する適用業務の中でも配列を用意して探索を行う場合にも応用できる。
RPG であれば LOOKUP によって配列内を検索することができるが LOOKUP も中では線形探索が
行われているのである。
二分探索のこの手法は覚えておいて損はないだろう。
何かのときにはこの記事があったことを思い出して欲しい。
【実行結果】
