使用 Java 的 DSA - 插值搜索

概述

插值搜索是二分搜索的改进版本。此搜索算法适用于所需值的探测位置。为了使此算法正常工作，数据集合应为排序形式。

插值搜索通过计算探测位置来搜索特定项目。最初，探测位置是集合最中间项目的位置。如果匹配，则返回项目的索引。如果中间项目大于项目，则再次在中间项目右侧的子数组中计算探测位置，否则，将在中间项目左侧的子数组中搜索项目。该过程也在子数组上继续，直到子数组的大小减小到零。

插值搜索的示例是字典搜索，其中搜索从 X 开始的单词，我们在字典末尾附近搜索，因此通过插值探测位置等。

算法

Interpolation Search ( A: array of item, n: total no. of items 
        ,x: item to be searched)
Step 1: Set lowerBound = 0
Step 2: Set upperBound = n - 1
Step 3: if lowerBound  = upperBound or A[lowerBound] = A[upperBound] 
        go to step 12
Step 4: set midPoint = lowerBound + 
        ((upperBound -lowerBound) / (A[upperBound] - A[lowerBound])) 
        * (x - A[lowerBound])
Step 5: if A[midPoint] < x
Step 6: set from = midPoint + 1
Step 7: if A[midPoint] > x
Step 8: set to = midPoint - 1 
Step 9  if A[midPoint] = x go to step 11
Step 10: Go to Step 3
Step 11: Print Element x Found at index midPoint and go to step 13
Step 12: Print element not found
Step 13: Exit

演示程序

package com.tutorialspoint.simplesearch;

import java.util.Arrays;

public class InterpolationSearchDemo {
    
   public static void main(String args[]){
      int[] sourceArray = {1,2,3,4,6,7,9,11,12,14,15,
      16,17,19,33,34,43,45,55,66,76,88};
      System.out.println("Input Array: " +Arrays.toString(sourceArray));
      printline(50);
      // 找到 55 的位置 //
      int location = find(sourceArray, 55);
      if(location != -1){
         System.out.println("Element found at location: " +(location+1));
      }else {
         System.out.println("Element not found.");
      }    
   }

   public static int find(int[] intArray, int data){
      int lowerBound = 0;
      int upperBound = intArray.length -1;
      int midPoint = -1;
      int comparisons = 0;      
      int index = -1;
      while(lowerBound <= upperBound){
         System.out.println("Comparison " + (comparisons +1) ) ;
         System.out.println("lowerBound : "+lowerBound  
                           + " , intArray[" + lowerBound+"] = " 
                           + intArray[lowerBound]) ;
         System.out.println("upperBound : "+upperBound  
                           + " , intArray[" + upperBound+"] = " 
                           + intArray[upperBound]) ;
         comparisons++;
         // 探测中点
         midPoint = lowerBound + 
         Math.round((float)(upperBound - lowerBound) 
            / (intArray[upperBound] - intArray[lowerBound]) 
            *  (data - intArray[lowerBound]));
         System.out.println("midPoint = "+midPoint);
         // 找到数据 
         if(intArray[midPoint] == data){
		    index = midPoint;
            break;
         }
         else {
            // 如果数据较大
            if(intArray[midPoint] < data){
               // 数据位于上半部分 
               lowerBound = midPoint + 1;
            }
            // 数据较小 
            else{           
               // 数据在下半部分 
               upperBound = midPoint -1;
            }
         }               
      }
      System.out.println("Total comparisons made: " + comparisons);
      return index;
   }
   
   public static void printline(int count){
      for(int i=0;i <count-1;i++){
         System.out.print("=");
      }
      System.out.println("=");
   }
}

如果我们编译并运行上述程序，则会产生以下结果 −

Input Array: [1 2 3 4 6 7 9 11 12 14 15 16 17 19 33 34 43 45 55 66 ]
==================================================
Comparison 1
lowerBound : 0, intArray[0] = 1
upperBound : 19, intArray[19] = 66
midPoint = 16
Comparison 2
lowerBound : 17, intArray[17] = 45
upperBound : 19, intArray[19] = 66
midPoint = 18
Total comparisons made: 2
Element found at location: 19