七⼤查算法（⼀）——顺序、折半、插值、斐波拉契、分块查定义：根据给定的某个值，在查表中确定⼀个其关键字等于给定值的数据元素（或记录）。 查算法分类：
1）静态查和动态查；
注：静态或者动态都是针对查表⽽⾔的。动态表指查表中有删除和插⼊操作的表。
⽆序查：被查数列有序⽆序均可； 有序查：被查数列必须为有序数列。
20q平均查长度（Average Search Length，ASL）：需和指定key进⾏⽐较的关键字的个数的期望值，称为查算法在查成功时的平均查长度。
对于含有n个数据元素的查表，查成功的平均查长度为：ASL = Pi*Ci的和。
Pi：查表中第i个数据元素的概率。
Ci：到第i个数据元素时已经⽐较过的次数。
顺序查
说明：顺序查适合于存储结构为顺序存储或链接存储的线性表。
基本思想：顺序查也称为线形查，属于⽆序查算法。从数据结构线形表的⼀端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相⽐较，若相等则表⽰查成功；若扫描结束仍没有到关键字等于k的结点，表⽰查失败。
复杂度分析： 查成功时的平均查长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
当查不成功时，需要n次⽐较，时间复杂度为O(n);
所以，顺序查的时间复杂度为O(n)。
优缺点分析：缺点是平均查长度较⼤，当n很⼤时，查效率较低。优点是：算法简单且适应⾯⼴。对表的结构⽆任何要求，⽆论记录是否按关键字有序均可应⽤。
实现源码：
//顺序查
int SequenceSearch(int[] a, int value, int n)
{
int i;
for (i = 0; i < n; i++)
{
if (a[i] == value)
{
return i;
}
}
return -1;
}
⼆分查（折半查）
说明：元素必须是有序的，如果是⽆序的则要先进⾏排序操作。
基本思想：也称为是折半查，属于有序查算法。⽤给定值k先与中间结点的关键字⽐较，中间结点把线形表分成两个⼦表，若相等则查成功；若不相等，再根据k与该中间结点关键字的⽐较结果确定下⼀步查哪个⼦表，这样递归进⾏，直到查到或查结束发现表中没有这样的结点。
复杂度分析：最坏情况下，关键词⽐较次数为，且期望时间复杂度为O(log2(n));
折半查是⼀棵⼆叉排序树，每个根结点的值都⼤于左⼦树的所有结点的值，⼩于右⼦树所有结点的值。
例如：长度为10的有序表的平均查长度为：ASL=(1*1+2*2+3*4+4*3)/10=29/10=2.9;
注：折半查的前提条件是需要有序表顺序存储（即顺序表），对于静态查表，⼀次排序后不再变化，折半查能得到不错的效率。但对于需要频繁执⾏插⼊或删除操作的数据集来说，维护有序的排序会带来不⼩的⼯作量，那就不建议使⽤。
优缺点分析：缺点是只适⽤于有序表，且限于顺序存储结构。优点是：效率更⾼。
实现源码：
//⼆分查（折半查），循环实现
int BinarySearch1(int[] a, int value, int n)
{
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (a[mid] == value)
return mid;
else if (a[mid] > value)
high = mid - 1;
else if (a[mid] < value)
low = mid + 1;
}
return -1;
}
//⼆分查，递归实现
int BinarySearch2(int[] a, int value, int low, int high)
{
if (low <= high)
{
int mid = low + (high - low) / 2;
if (a[mid] == value)
return mid;
if (a[mid] > value)
return BinarySearch2(a, value, low, mid - 1);
if (a[mid] < value)
return BinarySearch2(a, value, mid + 1, high);
}
return -1;
}
插值查
在介绍插值查之前，⾸先考虑⼀个新问题，为什么上述算法⼀定要是折半，⽽不是折四分之⼀或者折更多呢？打个⽐⽅，在英⽂字典⾥⾯查“apple”，你下意识翻开字典是翻前⾯的书页还是后⾯的书页呢？如果再让你查“zoo”，你⼜怎么查？很显然，这⾥你绝对不会是从中间开始查起，⽽是有⼀定⽬的的往前或往后翻。
同样的，⽐如要在取值范围1 ~ 10000 之间 100 个元素从⼩到⼤均匀分布的数组中查5， 我们⾃然会考虑从数组下标较⼩的开始查。
经过以上分析，折半查这种查⽅式，不是⾃适应的（也就是说是傻⽠式的）。⼆分查中查点计算如下：
mid=(low+high)/2, 即mid=low+1/2*(high-low);
通过类⽐，我们可以将查的点改进为如下：
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)
也就是将上述的⽐例参数1/2改进为⾃适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了⽐较次数。
基本思想：基于⼆分查算法，将查点的选择改进为⾃适应选择，可以提⾼查效率。当然，差值查也属于有序查。
复杂度分析：查成功或者失败的时间复杂度均为O(log2(log2(n))) 。
优缺点分析：对于表长较⼤，⽽关键字分布⼜⽐较均匀的查表来说，插值查算法的平均性能⽐折半查要好的多。反之，数组中如果分布⾮常不均匀，那么插值查未必是很合适的选择。
实现源码：
//插值查
int InsertionSearch(int[] a, int value, int low, int high)
{
if(low <= high)
{
int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
if(a[mid]==value)
return mid;
if(a[mid]>value)
return InsertionSearch(a, value, low, mid-1);
if(a[mid]<value)
return InsertionSearch(a, value, mid+1, high);
}
return -1;
}
斐波那契查
基本思想：也是⼆分查的⼀种提升算法，通过运⽤黄⾦⽐例（0.618⽐）的概念在数列中选择查点进⾏查，提⾼查效率。同样地，斐波那契查也属于⼀种有序查算法。
⽅法：斐波那契查与折半查很相似，他是根据斐波那契序列的特点对有序表进⾏分割的。他要求开始表中记录的个数为某个斐波那契数⼩1，即n=F(k)-1;
开始将k值与第F(k-1)位置的记录进⾏⽐较(及mid=low+F(k-1)-1),⽐较结果也分为三种：
1）相等，mid位置的元素即为所求；
2）>，low=mid+1,k -= 2;
说明：low=mid+1说明待查的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-
1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应⽤斐波那契查。
3）<，high=mid-1,k-=1。
说明：low=mid-1说明待查的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归 的应⽤斐波那契查。
复杂度分析：最坏情况下，时间复杂度为 O(log2(n)) ，且其期望复杂度也为 O(log2(n)) 。
原理：斐波那契查就是在⼆分查的基础上根据斐波那契数列进⾏分割的。原查列表长度为A，那么我们在Fibo数列中到⼀个等于或者刚好⼤于A的数F[n](这⾥F[n] >= A), 然后将原来查表长度扩展为 F[n]（以原列表最后⼀个值进⾏扩充，最⼤值扩充）. 再对这个新表进⾏Fibo分割。F[n] = F[n-1] + F[n-2]，所以⼀个长度为F[n] 的查表分为两个新的查表，长度分别为F[n-1] 和 F[n-2]。到要
查的元素在哪⼀部分，递归。
⽐如：arr={1，2，3，4，5，6，7，8，9，10，11，12}要对他进⾏斐波那契查，查的值是10。
该数组长度为12, Fibo = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}, 所以选取13作为新数组长度，这么⼀来新数组：
{1，2，3，4，5，6，7，8，9，10，11，12，12}
F[n] = F[n-1] + F[n-2], F[n] = 13, 所以F[n-1] = 8, F[n-2] = 5. 那么对应的位置是F[6] = F[5] + F[4], 中间值为 F[5] = 8.
到中间值了，接下来就是进⾏⽐较与递归。
优缺点分析：与折半查相⽐，斐波那契查的优点是它只涉及加法和减法运算，⽽不⽤除法，⽽除法⽐加减法要占⽤更多的时间，因此，斐波那契查的运⾏时间理论上⽐折半查⼩。缺点是引⼊了斐波拉契数列需要存储的额外空间，牺牲空间换取时间。
实现源码：
/// <summary>
/// ⽣成斐波那契数列
/// </summary>
/// <param name="fib">指向存储斐波那契数列的数组</param>
/// <param name="size">斐波那契数列长度</param>
void ProduceFib(int[] fib, int size)
{
int i;
fib[0] = 1;
fib[1] = 1;
for (i = 2; i < size; i++)
{
fib[i] = fib[i - 1] + fib[i - 2];
}
}
private const int Maxsize = 20; //斐波那契数组的长度
/// <summary>
/// 斐波那契查，查成功返回位序，否则返回-1
/// </summary>
/// <param name="data">有序表数组</param>
/// <param name="searchValue">待查关键字</param>
/// <returns></returns>
int FibonacciSearch(int[] data, int searchValue)
{
int low = 0;
int length = data.Length;
int high = length - 1;
int mid, k, i;
int[] fib = new int[Maxsize];
因为你英文ProduceFib(fib, Maxsize);
k = 0;
// 到有序表元素个数在斐波那契数列中最接近的最⼤数列值
while (high > fib[k] - 1)
{
k++;
}
// 补齐有序表
for (i = length; i <= fib[k] - 1; i++)
{
data[i] = data[high];
}
while (low <= high)寻求自我
{
面子理论
mid = low + fib[k - 1] - 1; // 根据斐波那契数列进⾏黄⾦分割
if (data[mid] == searchValue)
{
if (mid <= length - 1)
{
return mid;
}
else
{
// 说明查得到的数据元素是补全值
return length - 1;
}
}
if (data[mid] > searchValue)
计算机技术与发展
{
high = mid - 1;
k -= 1;
}
if (data[mid] < searchValue)
{
low = mid + 1;
k -= 2;
}
}
return -1;
}
分块查
要求是顺序表，分块查⼜称索引顺序查，它是顺序查的⼀种改进⽅法。
算法思想：将n个数据元素”按块有序”划分为m块（m ≤ n）。每⼀块中的结点不必有序，但块与块之间必须”按块有序”；即第1块中任⼀元素的关键字都必须⼩于第2块中任⼀元素的关键字；⽽第2块中任⼀元素⼜都必须⼩于第3块中的任⼀元素，……
算法流程：
1、先选取各块中的最⼤关键字构成⼀个索引表；tl7705
2、查分两个部分：先对索引表进⾏⼆分查或顺序查，以确定待查记录在哪⼀块中；
3、在已确定的块中⽤顺序法进⾏查。
时间复杂度：O(log(m)+N/m)
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议