[演算法] 插補搜尋法(Interpolation Search) 插補搜尋法假設資料呈直線分布，利用斜率公式來猜測鍵值的位置(m) ⇒ 用key及斜率來計算m對於已排序好的資料，利用已排序及直線斜率的特性來加快搜尋速度作法與二分搜尋法類似，差別在二分搜尋法：猜測鍵值在中間位置(middle)插補搜尋法：用直線斜率猜測鍵值位置一般而言，資料量愈大，數值分佈會愈平均，愈呈線性 ⇒ 資料量大時，插補搜尋法的效率會比二分搜尋法好插補搜尋法(Interpolation Search)資料需依大小先排序好m = (key - y₁)(x₂ - x₁)/(y₂ - y₁) + x₁將鍵值key與data[m]作比對key = data[m]：找到key < data[m]：縮小搜尋範圍 ⇒ x₂ = m - 1key > data[m]：縮小搜尋範圍 ...
查看完整內容

[演算法] 插補搜尋法(Interpolation Search)

• 插補搜尋法假設資料呈直線分布，利用斜率公式來猜測鍵值的位置(m) ⇒ 用key及斜率來計算m
• 對於已排序好的資料，利用已排序及直線斜率的特性來加快搜尋速度
• 作法與二分搜尋法類似，差別在
  • 二分搜尋法：猜測鍵值在中間位置(middle)
  • 插補搜尋法：用直線斜率猜測鍵值位置
• 一般而言，資料量愈大，數值分佈會愈平均，愈呈線性 ⇒ 資料量大時，插補搜尋法的效率會比二分搜尋法好
• 插補搜尋法(Interpolation Search)
  • 資料需依大小先排序好
  • m = (key - y₁)(x₂ - x₁)/(y₂ - y₁) + x₁
  • 將鍵值key與data[m]作比對
    • key = data[m]：找到
    • key < data[m]：縮小搜尋範圍 ⇒ x₂ = m - 1
    • key > data[m]：縮小搜尋範圍 ⇒ x₁ = m + 1
  • 重複上步驟，直到找到資料或搜尋範圍交叉(找不到)
• 特性：
  • 資料需事先排序
  • 支援隨機存取(Random Access)機制
  • 時間複雜度為Ο(log₂n)
• 時間複雜度(Time Complexity)
  • Ο(log₂n)~ Ο(n)
  • Best Case： Ο(log₂n)
    • 每次m都等於middle 
    ⇒ 每次搜尋範圍都減半
• Worst Case：Ο(n)
  • 每次搜尋範圍只減少一筆資料

來源:http://notepad.yehyeh.net/Content/Algorithm/Search/InterpolationSearch/InterpolationSearch.php