内挿探索法とは？

内挿探索法とは、整列済みデータに対し、探索値が範囲内のどのあたりにありそうかを比例計算で予測し、その位置から調べる探索法。補間探索ともいう。二分探索が常に中央を見るのに対し、値の分布を利用してより近い位置を狙う。値が一様に分布していれば平均O(log log n)と非常に速い。

ないそうたんさくほう

基本情報技術者試験の頻出用語／テクノロジ系

内挿探索法の意味

整列済みデータに対し、探索値が範囲内のどのあたりにありそうかを比例計算で予測し、その位置から調べる探索法。補間探索ともいう。二分探索が常に中央を見るのに対し、値の分布を利用してより近い位置を狙う。値が一様に分布していれば平均O(log log n)と非常に速い。

1〜1000の値が均等に並ぶ1000件の配列から950を探すとき、二分探索は500から始めるが、内挿探索は先頭寄り・末尾寄りを計算して約950番目の位置を最初に調べる。辞書で「わ」を末尾側から引く感覚に近い。

前提は「整列済み」かつ「値がほぼ一様に分布」の両方。分布が偏っていると予測が外れ続け、最悪O(n)まで劣化する。整列していないデータには使えない点は二分探索と同じ。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。