基本情報技術者 2017年 春期 午前（科目A） 問07

昇順配列による二分探索【午前解説】

正解の理由

解法ステップ

1. 問題の前提条件を確認：二分探索は「ソート済み」と「ランダムアクセス可能」が必要かを判定する。
2. 各選択肢を前提に照らし合わせる：昇順・ランダム配置・ハッシュ位置などを区別する。
3. 前提を満たす選択肢を選択する：昇順に配置されているもの（かつランダムアクセス可能）が正解となる。

選択肢別の誤答解説

• ア: 顧客番号から求めたハッシュ値が指し示す位置に配置されているデータ構造
  • ハッシュ法はハッシュ関数とテーブルにより高速な平均探索が可能だが、キー順に並んでいるとは限らず二分探索の前提を満たさない。範囲検索にも不向き。
• イ: 顧客番号に関係なく、ランダムに配置されているデータ構造
  • ランダム配置はソートされておらず、二分探索の中央比較による半減が成立しないため不適。
• ウ: 顧客番号の昇順に配置されているデータ構造
  • 正解。昇順で連続配置されていればインデックスで中央要素に直接アクセスでき、二分探索が適用可能。
• エ: 顧客番号をセルに格納し、セルのアドレス順に配置されているデータ構造
  • 「セルのアドレス順＝キー順」とは限らないため、キーの昇順が保証されなければ二分探索は適用できない。アドレス順は物理配置であり論理キー順とは別概念。

よくある誤解

• 「昇順に並んでいればどんな構造でもいい」は誤りです。連結リストのようにランダムアクセスできない構造では二分探索は効率を発揮しません。
• 「ハッシュより常に速い」と考えるのも誤りです。ハッシュ探索は期待値で平均 $O(1)$ を達成できますが、キー順検索や範囲検索が必要な場合は二分探索（ソート済み配列）が有利です。

補足コラム

• 二分探索が最も力を発揮するのは、読み出し主体でキーの順序が固定されている場合です。更新（挿入・削除）が頻繁だとソートの維持コストが高くなります。
• データ構造の選択は用途次第：単純探索や範囲検索（順序性が重要）にはソート済み配列＋二分探索、等価探索で高速性が最優先ならハッシュ表、頻繁な挿入削除には平衡二分木（BST、B木など）を検討します。
• 連結リストは要素の挿入は容易でも、二分探索の前提であるO(1)ランダムアクセスを満たさないため不向きです。

def binary_search(arr, key):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == key:
            return mid
        elif arr[mid] < key:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1  # 見つからない場合

# 使用例
data = [1001, 1003, 1005, 1010, 1020]  # 昇順
print(binary_search(data, 1010))  # 出力: 3

FAQ