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; } */