から




専門/H16/05

正解 Edit

4

検証 Edit

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;
}
  • Nが8であり,xが配列に含まれるとした場合,引数xと配列の要素を比較した回数の最小値と最大値
  • N=8なので,whileの条件 L < Rは真(0 < 7)となり、必ずwhileループに入る。
  • 1回目のループで検索対象にヒットした場合(最小値),
    		if(x < a[m]) R = m-1;
    		else if(x > a[m]) L = m+1;
    		else return 1;
    で関数を抜けるため,配列との比較回数は2回となる。
  • 最大値を考える。x > a[m]の場合の方がif ... else ifなので x < a[m]より比較回数が多いため, x > a[m]を検証する。
  • 配列を下表と仮定する。
    a[0]a[1][a[2]a[3]a[4]a[5]a[6]a[7]
    01234567
  • L = 0, R = N-1 = 8-1 = 7
  • ループ1週目
    • while条件 (L < R) = ( 0 < 7) = 真
      • m = (L+R)/2 = (0+7)/2 = 3
      • if(x < a[m]) R = m-1; // 1回目
      • else if(x > a[m]) L = m+1; // 2回目
        if条件 (x > a[3]) = 真, L = m+1 = 3+1 = 4
  • ループ2週目
    • while条件 (L < R) = ( 4 < 7) = 真
      • m = (L+R)/2 = (4+7)/2 = 5
      • if(x < a[m]) R = m-1; // 3回目
      • else if(x > a[m]) L = m+1; // 4回目
        if条件 (x > a[5]) = 真, L = m+1 = 5+1 = 6
  • ループ3週目
    • while条件 (L < R) = ( 6 < 7) = 真
      • m = (L+R)/2 = (6+7)/2 = 6
      • if(x < a[m]) R = m-1; // 5回目
      • else if(x > a[m]) L = m+1; // 6回目
        if条件 (x > a[6]) = 真, L = m+1 = 6+1 = 7
  • ループ3週目
    • while条件 (L < R) = ( 7 < 7) = 偽
      よってwhileループに入らず。
  • if(x == a[m] return 1; else return 0; // 7回目
    x == a[7]

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



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