內插搜尋 (Interpolation Search) 是一種基於數值分布估算落點的搜尋演算法，是對 二元搜尋 (Binary Search) 的改良。它特別適合用在已排序且元素分布相對均勻的資料集上，能有效地減少搜尋次數。

為什麼要用內插搜尋?

二元搜尋每次都「取中間」，假設資料大致均勻地分佈，但若目標值靠近開頭，仍會浪費許多比較。

舉例: 假設我們要找 3

• 資料是 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
• Binary Search 會先看中間 5，再往左看 2~4
• Interpolation Search 則會「預測」目標在偏左，第一次就可能落在 3 附近

核心概念: 根據數值的相對大小，估計出目標可能所在的位置。

公式原理

在每次搜尋中，透過「線性內插公式」計算預估位置 pos:

pos = left + (target - arr[left]) * (right - left) // (arr[right] - arr[left])

• left / right: 目前搜尋區間邊界
• arr[left] / arr[right]: 邊界的值
• target: 要搜尋的值
• pos: 根據比例估算出的落點位置

如果 arr[left] == arr[right](例如所有元素相同)，為避免除以 0，應直接檢查元素是否等於 target。

演算法步驟

• 設定 left = 0、right = n-1。
• 當 left <= right 且 target 介於 arr[left] 和 arr[right] 之間:
  • 用公式計算預估位置 pos
  • 若 arr[pos] == target → 回傳 pos
  • 若 arr[pos] < target → left = pos + 1
  • 若 arr[pos] > target → right = pos - 1

若未找到 → 回傳 -1

程式碼範例

def interpolation_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right and arr[left] <= target <= arr[right]:
        if arr[left] == arr[right]:
            if arr[left] == target:
                return left
            else:
                break

        # 根據比例計算預估位置
        pos = left + (target - arr[left]) * (right - left) // (arr[right] - arr[left])

        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    
    return -1

# 測試
arr = [10, 20, 30, 40, 50, 60, 70]
print(interpolation_search(arr, 40))  # 輸出: 3
print(interpolation_search(arr, 25))  # 輸出: -1

複雜度分析

• 平均情況: O(log log n)
  • 因為分布均勻時，每次能大幅縮小搜尋範圍，比 Binary Search 更快
• 最壞情況: O(n)
  • 若資料分布極度不均勻（例如大多數值集中在一邊），效果會急劇下降
• 空間複雜度: O(1)（原地搜尋）

與 Binary Search 的比較

結語

內插搜尋是一種在特定條件下非常高效的搜尋演算法，它的思維突破了「固定折半」，改用「依值推估位置」來直接逼近目標。

雖然在最壞情況下效能會退化，但如果資料分布均勻、且查詢遠多於更新操作，它能比 Binary Search 更快，是搜尋問題中一個非常值得認識的技巧。