上一节:
下一节:

  数据结构&算法 插入查找

  • 插入查找

    插入查找是二分查找的改进变体。该搜索算法在所需值的探测位置上工作。为了使该算法正常工作，数据收集应采用排序形式并平均分配。与线性搜索相比，二分查找具有时间复杂性的巨大优势。线性搜索的最坏情况复杂度为Ο(n)，而二分查找的复杂度为Ο(log n)。在某些情况下，可能会事先知道目标数据的位置。例如，在电话号码簿的情况下，如果我们要搜索Morphius的电话号码。在这里，线性搜索甚至二分查找似乎都很慢，因为我们可以直接跳转到名称以"M"开头的存储空间。

  • 二分查找中的定位

    在二进制搜索中，如果找不到所需的数据，则列表的其余部分分为左右两个部分。搜索在其中一个中进行。
    insertsearch
    即使对数据进行了排序，二分查找也无法利用它来探测所需数据的位置。

  • 插入查找中的位置探测

    插入查找通过计算探测器位置来找到特定项目。最初，探针位置是集合中最中间一项的位置。
    insertsearch
    如果发生匹配，则返回该项目的索引。要将列表分为两部分，我们使用以下方法- 
    
mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where −
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list
    如果中间项目大于该项目，则再次在中间项目右侧的子数组中计算探针位置。否则，将在中间项目左侧的子数组中搜索该项目。该过程同样在子数列上继续进行，直到子数列的大小减小到零为止。运行时插值搜索算法的复杂度为Ο(log(log n))相比，二分查找的Ο(log n) 是有利的情况。
    算法
    由于它是对现有二分查找算法的一种改进，因此我们提到了使用位置探测来搜索“目标”数据值索引的步骤- 
    
步骤 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
    用C编程语言实现插入查找- 
    
#include <stdio.h>

#define MAX 10

// array of items on which linear search will be conducted. 
int list[MAX] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };

int find(int data) {
   int lo = 0;
   int hi = MAX - 1;
   int mid = -1;
   int comparisons = 1;      
   int index = -1;

   while(lo <= hi) {
      printf("\nComparison %d  \n" , comparisons ) ;
      printf("lo : %d, list[%d] = %d\n", lo, lo, list[lo]);
      printf("hi : %d, list[%d] = %d\n", hi, hi, list[hi]);
      
      comparisons++;

      // probe the mid point 
      mid = lo + (((double)(hi - lo) / (list[hi] - list[lo])) * (data - list[lo]));
      printf("mid = %d\n",mid);

      // data found 
      if(list[mid] == data) {
         index = mid;
         break;
      } else {
         if(list[mid] < data) {
            // if data is larger, data is in upper half 
            lo = mid + 1;
         } else {
            // if data is smaller, data is in lower half 
            hi = mid - 1;
         }
      }               
   }
   
   printf("\nTotal comparisons made: %d", --comparisons);
   return index;
}

int main() {
   //find location of 33
   int location = find(33);

   // if element was found 
   if(location != -1)
      printf("\nElement 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
上一节:
下一节: