演習 アルゴリズム

要素数が n の配列に対して線形探索を行い、探している値が配列の中に1つも無かった。このときの比較回数として適切なものはどれか。

昇順に並んだ配列 data が {2, 5, 9, 14, 20, 27, 33} である。この配列から 27 を二分探索で探す。探索範囲の下端を low、上端を high とし、初期値をそれぞれ 1 と 7 とする。中央の位置 mid は (low + high) ÷ 2 の商で求め、data[mid] が探す値より小さければ low を mid + 1 に、大きければ high を mid - 1 に更新する。1 回目の比較を終えた直後の low と high の値はどれか。

配列 {8, 2, 6, 4} を交換法(バブルソート)で昇順に整列する。隣り合う2つを先頭から順に比べ、前のほうが大きければ入れ替える走査を1回だけ行った直後の配列はどれか。

配列 {6, 2, 9, 1, 5} をある方法で昇順に整列したところ、1 回目の走査を終えた時点で {1, 2, 9, 6, 5} になった。使われた整列法はどれか。

データの個数 n が非常に大きいとき、処理時間の増え方が最も緩やかなものはどれか。