插值搜索算法

插值搜索是二分查找的一种改进变体。该搜索算法作用于所需值的探测位置。为了使该算法正常工作，数据集合应为有序且均匀分布的集合。

二分查找在时间复杂度方面比线性搜索具有巨大的优势。线性搜索的最坏情况复杂度为 Ο(n)，而二分搜索的最坏情况复杂度为 Ο(log n)。

在某些情况下，目标数据的位置可能预先已知。例如，在电话簿中，如果我们想搜索"Morpheus"的电话号码。在这种情况下，线性搜索甚至二分搜索都会显得很慢，因为我们可以直接跳转到存储以"M"开头的姓名的内存空间。

二分搜索中的定位

在二分搜索中，如果未找到所需数据，则将列表的其余部分分为两部分：低位和高位。搜索可以在其中任意一个中进行。

即使数据已排序，二分查找也无法探测所需数据的位置。

插值中的位置探测搜索

插值搜索通过计算探测位置来查找特定项。最初，探测位置是集合中最中间项的位置。

如果匹配，则返回该项的索引。要将列表拆分为两部分，我们使用以下方法 −

$$mid\, =\, Lo\, +\, \frac{\left ( Hi\, -\, Lo ight )\ast \left ( X\, -\, A\left [ Lo ight ] ight )}{A\left [ Hi ight ]\, -\, A\left [ Lo ight ]}$$

其中 −

A = 列表
Lo = 列表的最低索引
Hi = 列表的最高索引
A[n] = 列表中存储在索引 n 处的值

如果中间项大于该项，则在中间项右侧的子数组中再次计算探测位置。否则，在中间项左侧的子数组中搜索该项。此过程在子数组上持续进行，直到子数组的大小减小到零。

插值搜索算法

由于它是对现有 BST 算法的改进，我们提到了使用位置探测 − 来搜索"目标"数据值索引的步骤。

1. 从列表中间开始搜索数据。
2. 如果匹配，则返回项目的索引并退出。
3. 如果不匹配，则探测位置。
4. 使用探测公式划分列表并找到新的中间值。
5. 如果数据大于中间值，则在更高的子列表中搜索。
6. 如果数据小于中间值，则在更低的子列表中搜索。
7. 重复此操作，直到匹配。

伪代码

A → Array list
N → Size of A
X → Target Value

Procedure Interpolation_Search()

   Set Lo → 0
   Set Mid → -1
   Set Hi → N-1

   While X does not match
      if Lo equals to Hi OR A[Lo] equals to A[Hi]
         EXIT: Failure, Target not found
      end if

      Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

      if A[Mid] = X
         EXIT: Success, Target found at Mid
      else
         if A[Mid] < X
            Set Lo to Mid+1
         else if A[Mid] > X
            Set Hi to Mid-1
         end if
      end if
   End While
End Procedure

分析

插值搜索算法的运行时复杂度为 Ο(log (log n))，而在有利情况下，二叉搜索树的复杂度为 Ο(log n)。

示例

为了理解插值搜索的逐步过程，让我们看一个例子并围绕它进行操作。

考虑下面给出的已排序元素数组 −

让我们搜索元素 19。

解决方案

与二分查找不同，此方法中的中间点使用以下公式选择−

$$mid\, =\, Lo\, +\, \frac{\left ( Hi\, -\, Lo ight )\ast \left ( X\, -\, A\left [ Lo ight ] ight )}{A\left [ Hi ight ]\, -\, A\left [ Lo ight ]}$$

因此，对于给定的数组输入，

Lo = 0, A[Lo] = 10
Hi = 9, A[Hi] = 44
X = 19

应用公式找到列表中的中间点，我们得到

$$mid\, =\, 0\, +\, \frac{\left ( 9\, -\, 0 ight )\ast \left ( 19\, -\, 10 ight )}{44\, -\, 10}$$

$$mid\, =\, \frac{9\ast 9}{34}$$

$$mid\, =\, \frac{81}{34}\,=\,2.38$$

由于 mid 是索引值，我们只考虑小数的整数部分。即 mid = 2。

将给定的关键元素 19 与 mid 索引中的元素进行比较，发现两个元素匹配。

因此，该元素位于索引 2 处。

实现

插值搜索是二分搜索的一种改进变体。该搜索算法作用于所需值的探测位置。为了使该算法正常工作，数据集合应为排序且均匀分布的形式。

#include<stdio.h>
#define MAX 10

// 将进行线性搜索的项目数组。
int list[MAX] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
int interpolation_search(int data){
   int lo = 0;
   int hi = MAX - 1;
   int mid = -1;
   int comparisons = 1;
   int index = -1;
   while(lo <= hi) {
      printf("Comparison %d 
" , comparisons ) ;
      printf("lo : %d, list[%d] = %d
", lo, lo, list[lo]);
      printf("hi : %d, list[%d] = %d
", hi, hi, list[hi]);
      comparisons++;
      
      // 探测中点
      mid = lo + (((double)(hi - lo) / (list[hi] - list[lo])) * (data - list[lo]));
      printf("mid = %d
",mid);
      
      // 找到数据
      if(list[mid] == data) {
         index = mid;
         break;
      } else {
         if(list[mid] < data) {
            
            // 如果数据较大，则数据位于上半部分
            lo = mid + 1;
         } else {
            
            // 如果数据较小，则数据在下半部分
            hi = mid - 1;
         }
      }
   }
   printf("Total comparisons made: %d", --comparisons);
   return index;
}
int main(){
   
   //找到 33 的位置
   int location = interpolation_search(33);
   
   // 如果找到元素
   if(location != -1)
      printf("
Element found at location: %d" ,(location+1));
   else
      printf("Element not found.");
   return 0;
}

Comparison 1 
lo : 0, list[0] = 10
hi : 9, list[9] = 44
mid = 6
Total comparisons made: 1
Element found at location: 7

#include<iostream>
using namespace std;
#define MAX 10

// 将进行线性搜索的项目数组。
int list[MAX] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
int interpolation_search(int data){
   int lo = 0;
   int hi = MAX - 1;
   int mid = -1;
   int comparisons = 1;
   int index = -1;
   while(lo <= hi) {
      cout << "Comparison " << comparisons << endl;
      cout << "lo : " << lo << " list[" << lo << "] = " << list[lo] << endl;
      cout << "hi : " << hi << " list[" << hi << "] = " << list[hi] << endl;
      comparisons++;
      
      // 探测中点
      mid = lo + (((double)(hi - lo) / (list[hi] - list[lo])) * (data - list[lo]));
      cout << "mid = " << mid;
      
      // 找到数据
      if(list[mid] == data) {
         index = mid;
         break;
      } else {
         if(list[mid] < data) {
            
            // 如果数据较大，则数据位于上半部分
            lo = mid + 1;
         } else {
            
            // 如果数据较小，则数据在下半部分
            hi = mid - 1;
         }
      }
   }
   cout << "
Total comparisons made: " << (--comparisons);
   return index;
}
int main(){
   
   //找到 33 的位置
   int location = interpolation_search(33);
   
   // 如果找到元素
   if(location != -1)
      cout << "
Element found at location: " << (location+1);
   else
      cout << "Element not found.";
   return 0;
}

Comparison 1
lo : 0 list[0] = 10
hi : 9 list[9] = 44
mid = 6
Total comparisons made: 1
Element found at location: 7

import java.io.*;
public class InterpolationSearch {
   static int interpolation_search(int data, int[] list) {
      int lo = 0;
      int hi = list.length - 1;
      int mid = -1;
      int comparisons = 1;
      int index = -1;
      while(lo <= hi) {
         System.out.println("Comparison " + comparisons);
         System.out.println("lo : " + lo + " list[" + lo + "] = " + list[lo]);
         System.out.println("hi : " + hi + " list[" + hi + "] = " + list[hi]);
         comparisons++;
         
         // 探测中点
         mid = lo + (((hi - lo) * (data - list[lo])) / (list[hi] - list[lo]));
         System.out.println("mid = " + mid);
         
         // 找到数据
         if(list[mid] == data) {
            index = mid;
            break;
         } else {
            if(list[mid] < data) {
               
               // 如果数据较大，则数据位于上半部分
               lo = mid + 1;
            } else {
               
               // 如果数据较小，则数据在下半部分
               hi = mid - 1;
            }
         }
      }
      System.out.println("Total comparisons made: " + (--comparisons));
      return index;
   }
   public static void main(String args[]) {
      int[] list = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
      
      //找到 33 的位置
      int location = interpolation_search(33, list);
      
      // 如果找到元素
      if(location != -1)
         System.out.println("Element found at location: " + (location+1));
      else
         System.out.println("Element not found.");
   }
}

Comparison 1
lo : 0 list[0] = 10
hi : 9 list[9] = 44
mid = 6
Total comparisons made: 1
Element found at location: 7

def interpolation_search( data, arr):
   lo = 0
   hi = len(arr) - 1
   mid = -1
   comparisons = 1
   index = -1
   while(lo <= hi):
      print("Comparison ", comparisons)
      print("lo : ", lo)
      print("list[", lo, "] = ")
      print(arr[lo])
      print("hi : ", hi)
      print("list[", hi, "] = ")
      print(arr[hi])
      comparisons = comparisons + 1

      #探测中点
      mid = lo + (((hi - lo) * (data - arr[lo])) // (arr[hi] - arr[lo]))
      print("mid = ", mid)

      #data found
      if(arr[mid] == data):
         index = mid
         break
      else:
         if(arr[mid] < data):
            
            #如果数据较大，则数据位于上半部分
            lo = mid + 1
         else:

            #如果数据较小，则数据在下半部分
            hi = mid - 1
   print("Total comparisons made: ")
   print(comparisons-1)
   return index

arr = [10, 14, 19, 26, 27, 31, 33, 35, 42, 44]
#找到 33 的位置
location = interpolation_search(33, arr)

#如果找到元素
if(location != -1):
   print("Element found at location: ", (location+1))
else:
   print("Element not found.")

Comparison  1
lo :  0
list[ 0 ] = 
10
hi :  9
list[ 9 ] = 
44
mid =  6
Total comparisons made: 
1
Element found at location:  7