━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 確認問題７
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問 (2分探索)

整数集合 S の要素 1, 2, 4, 6, 7, 9, 11, 14, 16, 18, 19, 22, 24 を
配列にこの順に格納し，2分探索で要素の所属判定をする．

次の各整数が集合 S に属すか否かを判定する際に，どの要素との比較が起こるかを，
比較した要素の系列として (例えば 1→4→7→11 のように) 示せ．

(1) 2

(2) 12

なお，中央値の位置(配列の添え字)は，探索範囲の開始位置が l で
終了位置が r のとき，整数の除算の商 div を使って次式で求めること．

        (l＋r) div 2

──────────────────────────────────────

●答 (2分探索)

(1) 11→4→1→2
(2) 11→18→14

[解説]

集合の要素を，次の表の通りに，配列 a[0..12] に格納する．

  i  | 0  1  2  3  4  5  6  7  8  9 10 11 12
-----+--------------------------------------
a[i] | 1  2  4  6  7  9 11 14 16 18 19 22 24

この場合，まず，探索の開始位置を l＝0，終了位置を r＝12 とおく．
比較位置は m ＝ (l + r) div 2 ＝ (0 + 12) div 2 ＝ 6 なので，a[6] つまり 11
と比較する．

(1) の探索では，探索する値が中央値未満 (2＜11) なので，2度目には，中央位置の
左側の要素と比べればよい．次の探索の開始位置は l＝0，終了位置は r＝5 となる．
探索する値が中央値と一致せずに探索を続けるとき，直前に比較した要素は，
次の探索範囲から除くことに注意する．2度目の比較位置は m ＝ (l + r) div 2 ＝
(0 + 5) div 2 ＝ 2 なので，a[2] つまり 4 と比較する．

(2) の探索では，探索する値が中央値を超える (11＜12) ので，2度目には，
中央位置の右側の要素と比べる．よって，次の探索の開始位置は l＝7，終了位置は
r＝12 となる．以降，同様の考え方で，値が見付かるか，探索区間が空になるまで
探索を続ける．

なお，配列の添え字を 0 以外から始めても，同じ結果になる．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/