明解 Javaによるアルゴリズムとデータ構造 3_探索

3-2 線形探索

単純な線形探索(順次探索)

1インデックスにつき、2つの条件文をチェックするコストが発生

  1. if index >= array.size() then search failed
  2. if array[i] = key then search succeeded

番兵法

1インデックスにつき、1つの条件文チェックでOK。単純な線形探索に比べて時間計算量が半分。

  • 一手間加える: 検索対象 array を1インデックス分拡張し、末尾要素に検索対象を代入
    • if array[i] = key のみで良い
    • return 時に、 i == 拡張したarray.size() ? -1 : i を仕込んどいて、-1 なら探索失敗って感じ

3-4 ハッシュ法

ハッシュ法 - データ追加/削除のコストを抑える

  • チェイン法(オープンハッシュ法)
    • 同一ハッシュ値のデータを、線形リストを用いてバケットに収納
  • オープンアドレス法(クローズドハッシュ法)
    • 同一ハッシュ値のデータは、再ハッシュにより、空いているバケットを探して収納
      • 線形探査法(linear probing) - 空きバケットに出会うまで再ハッシュを試行


明解 Javaによるアルゴリズムとデータ構造

明解 Javaによるアルゴリズムとデータ構造