2009 年度「計算数学１」 2009-06-01

§64 探索、特に二分探索

(64.1) int 型の配列 a[1], a[2], ..., a[N] に、 自然数が格納されているとする。 これとは別に、ある int 型変数 x に、 ある自然数が代入されているとする。 以上が与えられたとき、a[i] の中に x と値の等しいものがあるか、 あるとしたらどれか（i.e. x == a[i] となる i はいくつか） を求める問題を、「探索」（search）という。（「検索」とも言うかもしれない。）

(64.2) 一般に、探索のほうが整列（ソート）よりもやさしい。 よって、普通は、探索のほうを先に習う。

(64.3) 配列 a[ ] に収められている値に何ら規則性がなければ、 端から順に調べてゆくしかない。 この場合の比較の回数は、見つかる場合で平均して N/2 であり、 見つからない場合は N である。

(64.4) もしも a[i] に数値が狭義単調増加に格納されている（i.e. a[1] ＜ a[2] ＜ ... ＜ a[N] が成り立っている） とすると、端から順に調べるよりもはるかに効率のよい方法がある。

(64.5) それは、 「もしも x に等しいような a[i] があるとすればこことここの間（両端を含む）にある」 という範囲を、毎回毎回、約半分ずつにしてゆく方法である。

(64.6) その範囲の左の端の添え字を left, 右の端の添え字を right としよう。 最初の値はそれぞれ 1 と N である。 mid を、(left + right) / 2 と置く。 これは、その範囲のほぼまん中あたりを指す添え字である。そうしておいて、 x と a[mid] とを比べる。

これをくり返す。 範囲を約半分にするたびに 1 回か 2 回の比較を行なうので、 比較回数は最悪の場合でおよそ 2 log(N) 回である。 この方法を「二分探索」(binary search) と呼ぶ。

§65 課題７

(65.1) 次の書きかけプログラムを元に、各自で二分探索のプログラムを書け。

  1. まずは、関数 init() を、そこに書かれているコメントに従って完成させよう。 また、関数 print() は、前のソートのとき（ヒープソートは除く）と同じでよい。 そして、main() では、init() に続けて print() を呼び、 その次に、x の値を 「探すべき数は 18 です.」のように出力させるようにしよう。 ここまででコンパイル・実行してみて、 狭義単調増加数列で、隣り合った数の差が 1 か 2 のものが出力され、 探すべき数が 1 から a[N]+1 までのどれかであれば成功である。
  2. 次に、(64.6) に従って main() の肝心な部分を書き、 下の (65.3) に示したような出力例 --- 文言は全く同一でなくてもよい --- が得られるようにしてみよ。 なお、main() の途中に「return 0;」と書けば、 そこでプログラムは終了する。ループの途中で終わりたい場合に便利である。
  3. N を大きくして実験するようになったら、 print() の呼び出しはコメントとし、行わないようにする。 （それ以外の出力はされるように残してしておく。）

(65.2) 注意： ここでは、 見つからなかった場合に a[i] ＜ x ＜ a[i+1] を満たす a[i] と a[i+1] とを出力するようにするが、 x ＜ a[0] だった場合、 および a[N] ＜ x だった場合には、 （特別扱いをしなければ）a[0] や a[N+1] の値を出力してしまうことになる。 a[0] と a[N+1] を用意したのは、 この場合のことを考えてである。 探索の途中で a[0], a[N+1] にアクセスしてはいけない。 また、この場合もプログラムが正しく動くことを確かめるため、 関数 init() の中の「x = 」 の右辺を変更することでこのような場合を人為的に発生させ、チェックを行なうこと。 

#include <stdio.h>
#include <stdlib.h> /* srand() */
#include <time.h>   /* time() */

#define N 25

void init(void);
void print(void);

int a[1+N+1];       /* これで a[0] から a[N+1] までが使える */
int x;              /* これが探すべき数 */

main() {
    int left, right, mid;

    /* ここ（本体）を各自で考える */
}


void init(void) {
    int i;

    {   /* この中カッコの中（乱数の種の設定）はわからなくてもよい */
        unsigned seed = (unsigned)time(NULL);   /* 現在時刻を取得して */
        printf("乱数の種は %u です.\n", seed);
        srand(seed);                            /* それを乱数の種に */
    }

    /* ここに、a[0] = 0 から始めて、確率 1/2 で a[i+1] = a[i] + 1, 確率 1/2  */
    /* で a[i+1] = a[i] + 2, という漸化式で a[N] までを埋めるコードを書く。  */
    /* そうすれば、任意の自然数について、それが現れる確率は 1/2 となる。     */

    a[N+1] = 0;                     /* 念のためこうしておく */

    x =                             /* ここは、x が 1 から a[N]+1 までの値を */
                                    /* とるよう、乱数を用いて決める          */

    return;                         /* この return は普通は書かない */
}


void print(void) {
    /* ここはソートのときと全く同じでよい */
}

(65.3) 出力例１．（見つかった場合） 

配列の大きさは 25 です.
乱数の種は 1243748801 です.
02 04 06 07 09 11 13 14 16 18 20 21 23 24 25 26 27 28 29 30 32 34 36 37 39
探すべき数は 18 です.
見つかるとしたら a[1] から a[25] までの中からです.
18 を a[13] = 23 と比べます.
見つかるとしたら a[1] から a[12] までの中からです.
18 を a[6] = 11 と比べます.
見つかるとしたら a[7] から a[12] までの中からです.
18 を a[9] = 16 と比べます.
見つかるとしたら a[10] から a[12] までの中からです.
18 を a[11] = 20 と比べます.
見つかるとしたら a[10] から a[10] までの中からです.
18 を a[10] = 18 と比べます.
18 は a[10] にありました.
出力例２．（見つからなかった場合） 
配列の大きさは 25 です.
乱数の種は 1243748840 です.
02 03 04 05 07 08 09 11 12 13 14 15 17 18 20 22 23 25 27 28 29 30 32 34 36
探すべき数は 26 です.
見つかるとしたら a[1] から a[25] までの中からです.
26 を a[13] = 17 と比べます.
見つかるとしたら a[14] から a[25] までの中からです.
26 を a[19] = 27 と比べます.
見つかるとしたら a[14] から a[18] までの中からです.
26 を a[16] = 22 と比べます.
見つかるとしたら a[17] から a[18] までの中からです.
26 を a[17] = 23 と比べます.
見つかるとしたら a[18] から a[18] までの中からです.
26 を a[18] = 25 と比べます.
26 は見つかりませんでした.
参考までに：a[18] = 25, a[19] = 27.

(65.4) レポートはいつものようにメールで、

を貼り付けて提出すること。件名は「kadai7」とせよ。

岩瀬順一