二分探索法と線形探索法とは？
二分探索法と線形探索法とは、線形探索法はデータを先頭から順に調べる方式でO(n)の計算量。二分探索法は整列済みデータに対し中央値との比較で探索範囲を半分ずつに絞り込む方式でO(log n)の計算量。応用情報では、これらを使った具体的な比較回数の計算や、ハッシュ法・木構造による探索との性能比較が出題される。
にぶんたんさくほうとせんけいたんさくほう
二分探索法と線形探索法の意味
線形探索法はデータを先頭から順に調べる方式でO(n)の計算量。二分探索法は整列済みデータに対し中央値との比較で探索範囲を半分ずつに絞り込む方式でO(log n)の計算量。応用情報では、これらを使った具体的な比較回数の計算や、ハッシュ法・木構造による探索との性能比較が出題される。
二分探索法と線形探索法の具体例
100万件の整列済みデータに対する二分探索の最大比較回数は約20回（log2(1,000,000)≈20）で、線形探索の最大100万回と比べ圧倒的に少ない。
二分探索法と線形探索法は試験でどう引っ掛けられる？
二分探索は対象があらかじめ整列されていることが前提で、未整列のデータには使えない。整列にかかる時間まで含めると、1回だけ探すなら線形探索のほうが速いこともある。またデータ件数が少ないうちはO(log n)のほうが必ず速いとは限らない点、O(1)で探せるハッシュ法でも衝突が多発すれば線形探索並みに劣化する点も見落としやすい。
二分探索法と線形探索法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。