Cクイックリファレンス 第2版

7.8

 可変個数引数

119

素へのポインタを返す。違うなら、要素を含むと思われる配列の半分について自分自身を

再帰的に呼び出す。探索する配列の長さが 0に達したら、指定要素は存在しないので、再

帰は中止される。

例

7-8

 関数

binarySearch()

// binarySearch()

関数はソート済み配列を探索する

//

引数：

見つける要素の値

;

探索する

long

配列

;

配列長

//

戻り値：

見つけた要素へのポインタまたは要素が配列になければ

NULL

const long* binarySearch(const long val, const long array[], const int n)

{

const int m = n / 2;

if (n <= 0) { return NULL; }

if (val == array[m]) { return array + m; }

if

(val < array[m]) { return binarySearch(val, array, m); }

else { return binarySearch(val, array + m + 1, n - m - 1); }

}

n

要素配列では、二分探索アルゴリズムは高々 1＋log

2

(

n

)回の比較をする。百万要素で

最大比較回数は20、

binarySearch()

関数が高々 20回再帰をするという意味だ。

再帰関数は、自動変数が再帰呼び出しごとに新しく作られるということに依存している。

これらの変数と戻りジャ ...