STEP 4.6 二分探索 (再帰)

STEP2.2 の 二分探索を、再帰で実装しよう。

<問題> 整数が昇順に整列された大きさN(10)の配列s (data)に整数keyがあるかを判定する。ある場合は、インデックスを示す。なければ、ないとプリントする。

入力:整数key
出力:配列sに整数keyがある場合は、インデックスを出力。 ない場合も、その旨、出力

<実行例>

探索キーを入力してください :14
s[0] = 1
s[1] = 3
s[2] = 4
s[3] = 8
s[4] = 13
s[5] = 14
s[6] = 18
s[7] = 20
s[8] = 21
s[9] = 25
14 is found in s[5]

探索キーを入力してください :23
s[0] = 1
s[1] = 3
s[2] = 4
s[3] = 8
s[4] = 13
s[5] = 14
s[6] = 18
s[7] = 20
s[8] = 21
s[9] = 25
The element 23 is not in s


<ヒント>

例題集へ



解答例

#include <stdio.h>

#define N 10
int s[N] = {1,3,4,8,13,14,18,20,21,25};

void print_data (void);  /* 配列のプリント */
int binary_search (int key, int low, int high);
/* 引数はkey, low, high。見つけた場合の添え字を戻す。*/

int main (void) {
    int x;
    int i; /* なぜかlong iとなっている人がいますが、int iで十分 */

    printf("探索キーを入力してください :");
    scanf("%d", &x);

    print_data();

    i = binary_search(x, 0, N-1); /* 検索せよ。戻り値をiに代入 */

    /* iの値をチェック */
    if (i == -1 ) /* 見つけていない */
        printf("The element %d is not in s\n", x);
    else
        printf("%d is found in s[%d]\n", x,i);


    return 0;
}

void print_data (void) {
    int i;

    for (i = 0; i < N ; i++)
         printf("s[%d] = %d \n", i, s[i]);
}

/* 再帰版 */
int binary_search(int key, int low, int high) {

  作成しよう
}

/* 参考: 非再帰。whileループ版
int binary_search(int key) {

    int low = 0 ;
    int high = N - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) /2;
        printf("low = %2d, high = %2d, mid = %2d \n", low, high, mid);
        if (s[mid] == key ) {
            return (mid);
        }
        if (s[mid] > key)
            high = mid - 1;
        else
            low = mid + 1 ;
     }

   r eturn -1;
}

*/