から




IV-5 Edit

C言語の関数bsearchを以下のように定義する。渡される引数は,ソートされた整数の配列,その要素数,および,探索すべき値である。配列内を探して見つかった場合は1を,見つからなかった場合は0を返す。

int bsearch(int a[], int N, int x){
	int L, R, m;
	L = 0; R = N-1;
	while (L < R){
		m = (L+R)/2;
		if(x < a[m]) R = m-1;
		else if(x > a[m]) L = m+1;
		else return 1;
	}
	if(x == a[m] return 1; else return 0;
}

この関数を呼び出した場合,引数xと配列の要素を比較した回数の総和は,配列の内容と引数xの値に応じて様々である。Nが8であり,xが配列に含まれるとした場合,比較回数の最小値と最大値を次の中から選べ。

  1. 最小値1回,最大値3回
  2. 最小値1回,最大値7回
  3. 最小値1回,最大値6回
  4. 最小値2回,最大値7回
  5. 最小値2回,最大値8回

memo Edit


Tag: C言語の実行結果 探索



トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 下位頁新規  一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-22 Mon 23:18:40 JST (3100d)