内挿探索
2分探索ではリストの中央の値を基準として探索を行いますが、内挿探索は、この基準の決め方を工夫することで、探索をより効率的に行おうとする検索方法です。
要素が均一に分布している場合は、内挿探索は平均して\(log（log（n））\)、最悪の場合、最大\(O（n）\)の時間計算量になるそうです。
英語では’ Interpolation Search’ で、 ‘ Interpolation ‘は「内挿」「補間」と訳されます。
Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values). It was first described by W. W. Peterson in 1957.[1] Interpolation search resembles the method by which people search a telephone directory for a name (the key value by which the book’s entries are ordered): in each step the algorithm calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation. The key value actually found at this estimated position is then compared to the key value being sought. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position. This method will only work if calculations on the size of differences between key values are sensible.
From Wikipedia, the free encyclopedia
以下意訳。
内挿探索は、キーに割り当てられた数値（キー値）に従い並べられた配列内のキーを検索するアルゴリズムです。 1957年にW. W.ピーターソンが考案しました。内挿探索は、人々が電話帳で名前（電話帳のキー値）を探す方法に似ています：各ステップで、アルゴリズムは、 検索スペースの境界のキーの値と検索対象のキーの値に基いて 「線形補間」を行うことで 、探索する対象が残りの探索スペースのどこにあるかを計算します。 次に、この位置で実際に見つかったキー値を、探索しているキー値と比較します。 等しくない場合、2分探索と同じように比較することで、残りの探索スペースを実際に見つかったキー値の前後のどちらかに絞ります。 内挿探索を行うためには、キー値間の差のサイズの計算が適切でなければなりません。
内挿
内挿（ないそう、英: interpolation、補間とも言う）とは、ある既知の数値データ列を基にして、そのデータ列の各区間の範囲内を埋める数値を求めること、またはそのような関数を与えること。またその手法を内挿法（補間法）という。内挿するためには、各区間の範囲内で成り立つと期待される関数と境界での振舞い（境界条件）を決めることが必要である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
Wikipedia を見ると分かるように、内挿方法には様々な種類があり、よって、内挿探索にも様々なバリエーションがあると考えられますが、 ‘ Interpolation Search’ では、「線形補間」を使い、基準 \(mid \)を以下のような式で求めます。
$$ mid = low + ( (x-arr[low])*(high – low) / (arr[high]-arr[low]) ) $$
探索する要素 \(x\) が\(arr [high]\)に近い場合は\(mid \) はより high に近い高い値、\(arr [low]\) に近い場合は \(mid\) はより low に近い小さい値になります。
import random
def interpolation_search(lst, target_val):
low = 0
high = len(lst) - 1
# ２分探索からの書き換え
while lst[low] <= target_val and lst[high] >= target_val:
# ２分探索からの書き換え
mid = low + (target_val - lst[low]) * (high - low) // (lst[high] - lst[low])
if lst[mid] > target_val:
high = mid - 1
elif lst[mid] < target_val:
low = mid + 1
else:
return mid
return False
def print_serach_result(lst, target_val):
target_index = interpolation_search(lst, target_val)
if target_index:
print(f'{target_val}は{target_index+1}番目に見つかりました。')
else:
print(f'{target_val}はリストの中にありません。')
if __name__ == '__main__':
# 適当なリストの生成
random.seed(1)
lst = [random.randint(1, 100) for _ in range(10)]
lst.sort()
# [9, 16, 18, 33, 58, 61, 64, 73, 98, 98]
print(lst)
# 線形探索
# 64は7番目に見つかりました。
print_serach_result(lst, 64)
# 63はリストの中にありません。
print_serach_result(lst, 63)