2分探索法
Binary Search
にぶんたんさくほう
整列済みデータの中央値と目的の値を比較し、探索範囲を半分に絞り込みながら探索するアルゴリズム。データ量が多い場合でも高速に探索できるが、データが事前にソートされている必要がある。
アルゴリズムとプログラミング > アルゴリズムとプログラミング
他の資格での定義
関連キーワードの用語
IP線形探索法
データの先頭から順に1つずつ目的の値と比較して探索するアルゴリズム。実装が簡単だが、データ量に比例して探索時間が増加するため、大量のデータには不向きである。
FE線形探索法
データを先頭から順に目的の値と比較していく探索アルゴリズム。計算量はO(n)。データが整列されていなくても使用できるが、データ数が多い場合は非効率。逐次探索とも呼ばれる。
FEハッシュ表探索法
ハッシュ関数を用いてキーからデータの格納位置を直接計算して探索するアルゴリズム。平均計算量はO(1)で非常に高速。衝突が多発すると性能が低下する。
APハッシュ表探索法
キーからハッシュ関数でアドレスを算出し、データを直接参照する探索法。平均O(1)で探索可能だが、衝突(異なるキーが同一アドレスに対応)が発生した場合の処理が性能に影響する。シノニム対策が重要。
IPアルゴリズム
問題を解決するための手順や計算方法を明確に定義したもの。有限回の操作で必ず終了し、正しい結果を得られることが求められる。
IPフローチャート(流れ図)
アルゴリズムや処理の流れを図形記号で視覚的に表現した図。端子・処理・判断・ループなどの記号を矢印で結び、処理の順序や分岐を明確にする。