插值搜索是二分搜索的改进变体,该搜索算法在所需值的探测位置上工作,为了使该算法正常工作,数据收集已排序并平均分配。
与线性搜索相比,二分搜索具有时间复杂性的巨大优势,线性搜索的最坏情况复杂度为Ο(n),而二分搜索的复杂度为Ο(log n)。
在二分搜索中,如果找不到所需的数据,则列表的其余部分分为上下两个部分。搜索在其中任何一个中进行。
即使对数据进行了排序,二分搜索也无法利用它来探测所需数据的位置。
插值搜索通过计算探测器位置来找到特定值。最初,探针位置是集合中最中间一项的位置。
如果发生匹配,则返回该值的索引。要将列表分为两部分,我们使用以下方法-
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)),而BST的Ο(log n)在有利的情况下。
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
#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; }
上面的程序生成以下输出-
来源:LearnFk无涯教程网
Comparison 1 lo : 0, list[0]=10 hi : 9, list[9]=44 mid=6 Total comparisons made: 1 Element found at location: 7
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)