問題2 解説

 この問題も 1 番と同様に易しい問題である.文字を扱うことと,配列を使う必要があることくらいが 1 番と違う点である.

 まず,入力ファイルの 2 行目から n + 1 行目までのデータを読んで,変換表を 2 次元配列に格納する. 次いで,変換する文字を 1 文字ずつ読み込み,その文字を変換表から検索し,対応する文字を出力する. 変換表は大きさが小さいので,このときの検索方法は単純に順番に比較する方法で十分である.
 このような誰でも思いつくような単純な探索法にも名前が付いていて,線形探索 (linear search) と呼ばれている.それに対し,大きさの順に並んでいるデータ集合からあるデータ x を探索するとき,全体の中央のデータ c と x を比較し,

  1. x = c なら,見つかったので終了.
  2. x<c なら,c より小さい方の半分のデータの中で同じ方法(再帰呼び出し)で x を探索する.
  3. x>c なら,c より大きい方の半分のデータの中で同じ方法(再帰呼び出し)で x を探索する.
という探索法を 2 分探索 (binary search) という(上記の 2., 3. では「再帰呼び出し」と書いたが,もちろん再帰を使わなくてもまったく同じことができる).データの個数が n であるとき,線形探索法では探索にかかる時間が n に比例するのに対し,2 分探索法では探索にかかる時間は悪くても高々 log n に比例する時間以下であるので,非常に高速である.