查找算法总结 | RoseOu's blog

文章目录

1. 一、查找算法的相关概念
2. 二、六种查找算法

一、查找算法的相关概念

关键字的定义： 关键字是数据元素中某个数据项的值，用它可以标识一个数据元素。
查找的定义： 用关键字标识数据元素，查找时根据给定的值，在表中确定一个关键字的值等于给定值的记录或数据元素。
查找算法的分类：
(1).无序查找和有序查找：无序查找即被查找数列有序无序均可.有序查找即被查找数列必须为有序数列。
(2).静态查找和动态查找：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
平均查找长度（ASL）： 查找过程中先后和给定值进行比较的数据元素的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL=∑Pi*Ci (i=1,2,3,…,n)。
Pi：查找表中第i个数据元素的概率,且∑Pi=1（i=1,2,3,…,n）
Ci：找到第i个数据元素（其关键字等于给定值）时和给定值进行过比较的关键字的个数，显然，Ci的值随查找过程的不同而不同。

二、六种查找算法

以下所有算法讨论涉及的数据元素统一定义为如下描述的类型：

typedef int KeyType;  //关键字类型以int为例

typedef struct{
    KeyType key;
} ElemType;

注意： 每个算法只给出核心代码，完整代码请到我的Github。

1.顺序查找

介绍： 顺序查找也称为线形查找，属于无序查找算法。
算法思想： 从线形表的第一个元素的关键字起，依次和给定值进行比较，若某个关键字与给定值相等，则查找成功；反之，若直到扫描结束其关键字和给定值比较都不相等，则表明表中没有所查的记录，查找失败。

C++描述：

typedef struct{
    ElemType *elem;
    int length;  //表中数据元素个数
} SSTable;

int SqSearch(SSTable ST, KeyType kval){ //kval为需要查找的给定值
    for(int i=1;i<ST.length+1;i++){  //依次和给定值进行比较
        if (ST.elem[i].key==kval){  //若某个元素的关键字与给定值相等，则查找成功
            return i;    //返回数据元素所在的顺序
        }
    }
    return 0;   //直到扫描结束仍然没有数据元素的关键字与给定值相等，查找失败，返回0
}

由于在循环条件中必须加上不使循环变量出界的判别，那么当数据元素个数超过1000时，因判出界操作的时间消耗很可观，它将使整个算法的执行时间几乎增加一倍，为此，可类似于插入排序的算法，在数组的“0下标”处增设“哨兵”，并令查找过程自最后一个元素的关键字开始。
C++描述：

int SqSearch(SSTable ST, KeyType kval){
    int i;
    ST.elem[0].key=kval;
    for(i=ST.length;ST.elem[i].key!=kval;--i);
    return i;
}

平均查找长度： 当查找成功时，ASL = 1/n(1+2+3+…+n) = (n+1)/2。
时间复杂度分析： 当查找不成功时，需要n+1次比较，所以时间复杂度为O(n)。

2.折半查找

介绍： 也称二分查找，属于有序查找算法。数据元素必须是有序的，如果是无序的则要先进行排序操作。
算法思想： 用给定值先与中间数据元素的关键字比较，中间的数据元素把线形表分成两个子表，若相等则查找成功；若不相等，再根据给定值与该中间数据元素关键字的比较结果确定下一步查找哪个子表，这样逐步缩小范围，直至找到该记录，或者当查找区间缩小到0也没有找到等于给定值的关键字为止。

C++描述：

typedef struct{
    ElemType *elem;
    int length;  //表中数据元素个数
} SSTable;

//非递归实现
int BinarySearch(SSTable ST, KeyType kval)
{
    int low, high, mid;
    low = 1;
    high = ST.length;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(ST.elem[mid].key > kval){
            high = mid-1;
        }else if(ST.elem[mid].key < kval){
            low = mid+1;
        }else{
        	return mid;
        }
    }
    return 0;
}

//递归实现
int BinarySearch(SSTable ST, KeyType kval, int low, int high)
{
    int mid = low+(high-low)/2;
    if(ST.elem[mid].key > kval){
        return BinarySearch(ST, kval, low, mid-1);
    }else if(ST.elem[mid].key < kval){
        return BinarySearch(ST, kval, mid+1, high);
    }else{
        return mid;
    }
}

平均查找长度： ASL = ((n+1)/n * log(n+1))-1。
对于任意表长n大于50的有序表，其折半查找的平均查找长度近似为：ASL ≈ log(n+1)-1。
可以通过构造二叉判定树计算，如：

时间复杂度分析： 最坏情况下，关键词比较次数为log(n+1)，且期望时间复杂度为O(logn)。
注意： 可见折半查找的效率好于顺序查找，特别在表长较大时，其差别更大。但折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

3.分块查找

介绍： 分块查找又称索引顺序查找，实际上它是顺序查找的一种改进方法。其性能介于顺序查找和折半查找之间，它适合对“分块有序”的数据元素进行查找操作。
算法思想： 将n个数据元素按”分块有序”划分为m块（m ≤ n），所谓“分块有序”是指数据元素可按其关键字的大小分成若干“块”，且“前一块”中的最大关键字小于“后一块”中的最小关键字，而各块内部的数据元素不一定有序。然后先从各块中抽取最大数据元素构成一个索引表，由于数据元素分块有序，所以索引表是有序的。接下来查找过程分两步进行：先在索引表中进行折半或顺序查找，以确定待查记录的“所在块”，然后在已限定的那一块中进行顺序查找。

要注意的是，一般把下标为0的空间空出来。
C++描述：

typedef struct{
    ElemType *elem;
    int length;  //表中数据元素个数
} SSTable;

typedef struct{
    KeyType key;
    int stadr;
} indexItem;

typedef struct{
    indexItem *elem;
    int length;
} indexTable;

int Search_Idx(SSTable ST, indexTable ID, KeyType kval){
    int low,high,mid,s,t,k;
    bool found;

    //在顺序表ST中分块查找等于给定值kval的数据元素，ID为索引表
    //若找到，则返回该数据元素在ST中的位置，否则返回0
    low=0;
    high=ID.length-1;
    found=false;
    if(kval>ID.elem[high].key){ //当给定值kval比表中所有数据元素都大
        return 0;
    }
    while(low<=high && !found){ //折半查找索引表，确定查找区间
        mid=(low+high)/2;
        if(kval<ID.elem[mid].key){
            high=mid-1;
        }else if(kval>ID.elem[mid].key){
            low=mid+1;
        }else{
            found=true;low=mid;
        }
    }//while
    s=ID.elem[low].stadr;  //经索引表查找后，下一步的查找范围定位在第low块
    if(low<ID.length-1){
        t=ID.elem[low+1].stadr-1;
    }else{
        t=ST.length;     //s和t为在ST表进行查找的下界和上界
    }
    if(ST.elem[t].key==kval){
        return t;
    }else{          //在ST.elem[s]至ST.elem[t-1]的区间内进行顺序查找
        ST.elem[0]=ST.elem[t];   //ST.elem[0]用来暂存ST.elem[t]
        ST.elem[t].key=kval;        //设置哨兵
        for(k=s;ST.elem[k].key!=kval;k++);
        ST.elem[t]=ST.elem[0];   //回复暂存值
        if(k!=t){
            return k;
        }else{
            return 0;
        }
    }
}

平均查找长度： 由于分块查找实际上是进行了两次查找，则整个算法的平均查找长度是两次查找的平均查找长度之和。假设索引表的长度为b，顺序表的长度为n，则以二分查找确定块时整个分块查找的平均查找长度为：
ASL(n)=ASL(b)+ASL(n/b)≈log(b+1)-1+(n/b+1)/2。
注意： 一般情况下为进行索引顺序查找，不一定要将顺序表等分成若干块并提取每块的最大关键字作为索引项，有时也可根据顺序表中的关键字的特征来分块。

4.插值查找

介绍： 在介绍插值查找之前，我们想想，为什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？打个比方，要在取值范围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，这样也就间接地减少了比较次数。
算法思想： 基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，插值查找也属于有序查找。
C++描述：

typedef struct{
    ElemType *elem;
    int length;  //表中数据元素个数
} SSTable;

int InsertionSearch(SSTable ST, KeyType kval, int low, int high)
{
    int mid = low+((kval-ST.elem[low].key)*(ST.elem[high].key-ST.elem[low].key)/(ST.elem[high].key-ST.elem[low].key));
    if(ST.elem[mid].key > kval){
        return InsertionSearch(ST, kval, low, mid-1);
    }else if(ST.elem[mid].key < kval){
        return InsertionSearch(ST, kval, mid+1, high);
    }else{
        return mid;
    }
}

时间复杂度分析： 查找成功或者失败的时间复杂度均为O(log(logn))。
注意： 对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

5.二叉树查找

二叉查找树介绍： 二叉查找树也叫二叉排序树，它或者是一棵空树，或者是具有下列性质的二叉树：
（1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）任意节点的左、右子树也分别为二叉查找树。
算法思想： 对待查找的数据元素生成二叉查找树，然后将给定值和根结点的关键字进行比较，若相等，则查找成功，否则依据给定值小于或大于根结点的关键字，继续在左子树和右子树中进行查找，直至查找成功或者因左子树或右子树为空树为止，后者说明查找不成功。这个算法的查找效率很高，但是如果使用这种查找方法要首先创建二叉查找树。

注意： 这里要注意与折半查找的二叉判定树区分，二叉判定树是用来分析某个算法而设计的二叉树，而二叉排序树是用来对一组关键字进行排序的方法。
C++描述：

typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

//创建二叉查找树
void Insert_BST(BiTree &T,KeyType e){
	BiTNode *s,*p,*f;

	//在以T为根指针的二叉排序树中插入记录e
	s=new BiTNode;
	s->data.key=e;
	s->lchild=NULL;
	s->rchild=NULL;

	if(!T){
		T=s;
	}else{
		p=T;
		while(p){
			if(e<p->data.key){
				f=p;
				p=p->lchild;
			}else{
				f=p;
				p=p->rchild;
			}
		}
		if(e<f->data.key){
			f->lchild=s;
		}else{
			f->rchild=s;
		}
	}
}

//查找
bool Search_BST(BiTree T, KeyType kval,BiTree &p,BiTree &f){
	p=T;
	while(p){
		if(kval==p->data.key){
			return true;
		}else if(kval<p->data.key){
			f=p;
			p=p->lchild;
		}else{
			f=p;
			p=p->rchild;
		}
	}
	return false;
}

6.哈希查找

介绍： 在上述的查找中，由于数据元素在线性表中的存储位置是随机的，和关键字无关，因此在查找时，需将给定值和线性表中记录的关键字逐个比较，查找的效率基于历经比较的关键字的个数。设想，若在数据元素的关键字和其存储位置（数组下标）之间建立一个确定的函数关系f，即将关键字为key的记录存储在下标为Hash(key)的位置上，这样在查找关键字等于给定值kval的记录时，仅需直接对给定值进行某种运算，求得记录的存储位置Hash(kval)，而不需要和其他记录的关键字进行比较。按这种方法组织数据，在进行查找时将会有效减少针对关键字的比较次数，也就可以从根本上降低平均查找长度ASL的值。而哈希查找就是通过计算数据元素的存储地址进行查找的一种方法。
哈希函数： Hash(key)称为哈希函数。
冲突： 对不同的关键字key1和key2得到相同的哈希地址（即哈希函数值）Hash(key1)=Hash(key2)的这种现象称为冲突。在设定哈希函数时要考虑不发生冲突，然而实际上不发生冲突的哈希函数极少存在，只能设定对给定的关键字集合冲突尽可能少的哈希函数，在产生冲突时进行再散列，即为那些哈希地址位置已被其他记录占用的记录安排另外的存储位置。因此在建哈希表的时候，不但要设定一个哈希函数，还要设定一个处理冲突的方法。
哈希表： 哈希表是根据设定的哈希函数和处理冲突的方法为一组数据元素建立的一种存储结构。哈希函数又称散列函数，构造哈希表的方法又称散列技术。
装填系数： 假设哈希表的空间大小为m，在表中填入的数据元素数为n，定义a=n/m为哈希表的装填系数，实际应用时，常取a为0.65~0.85.
构造哈希函数的方法：
（1）除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址，即设定哈希函数为Hash(key)=key mod p (p<=m)。通常取p为不大于表长且最接近表长m的素数。如当哈希表表长为1000，可取p=977。
（2）平方取中法：取关键字平方后的中间几位为哈希地址，因为一个数的平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突。若哈希表表长为1000，则可取关键字平方值的中间3位。比如关键字为1234，那么1234²=1522756，可取227作为地址。
（3）折叠法：将关键字分割成位数相同的几部分（最后一部分位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。当关键字的位数很多且每一位的值都随机出现时，采用这种方法可得到冲突较少的哈希地址。
a. 移位叠加：将分割后的每一部分的最低位对齐，然后相加。如key=123456789，H(key)=123+456+789=1368。
b. 间界叠加：从一端向另一端沿分割界来回折叠，然后对齐相加。如key=123456789，H(key)=123+654+789=1566。
处理冲突的方法：
（1）开放地址法
从哈希函数求得一个地址序列H[1],H[2],…,H[k]，即哈希表中下标为H[1]，H[2]，H[k-1]的存储空间都已有记录，直至下标H[k]为空（若哈希表不满，必能找到k<=m-1）。即 H[i]=(Hash(key)+d[i]) mod m , Hash(key)为哈希函数，m为哈希表的表长，d[i]为增量序列。
增量序列的取法有下列三种：
a. d[i]=1,2,3,…,m-1,称为线性探测再散列。这种取法最简单，只要哈希表没填满就总能找到一个空的位置，但容易对之后填入的记录增加冲突。
b. d[i]=1², -1², 2², -2²,…,k²,-k²（k<=m/2），称为二次探测再散列。这种取法要求表长m必须是形如4j+3(j=1,2,…)的素数，如7,11,19,23,…等。
c. d[i]是一个伪随机序列，称为随机探测再散列。用这种取法时需选择一个伪随机函数产生伪随机数列，且在建表装填和查找时应使用同一个伪随机函数来生成伪随机数列。
（2）链地址法
将所有key对应的Hash(key)相同的记录存储在同一线性链表中，而哈希表中下标为i的空间存储哈希函数值为i的链表头指针。

算法流程： 哈希表的查找过程和建表过程一致，以开放地址处理冲突线性探测再散列为例。假设哈希函数为Hash(x)，则查找过程为：对给定值kval，求得哈希地址为j=Hash(kval)，若哈希表中下标为j的空间为空，则查找不成功，可将关键字等于kval的记录填入；若表中该空间不空且所填记录的关键字等于kval，则查找成功，否则按建表时设定的散列方法重复计算处理冲突后的各个地址，直至表中相应空间为空或者所填记录的关键字等于kval，前者表示查找不成功，后者查找成功。
C++描述：

const int NULLKEY=0;

typedef struct{
	ElemType *elem;
	int count;
} HashTable;

int Hash(int kval){   //除留余数法
	return kval%NUM;
}

void Next(int &p, int &c){   //线性探测再散列
	p=(p+1)%LENGTH;
}

int HashSearch(HashTable H, KeyType kval,int &p,int &c){
	//在开放定址哈希表H中查找关键码为kval的元素，
	//若查找成功，以p指示待查记录在表中位置,并返回p；否则，以p指示插入位置，并返回-1；
	//以c计算冲突次数，其初值置0，供建表插入时参考
	p=Hash(kval);   //求得哈希地址
	while (H.elem[p].key != NULLKEY && (H.elem[p].key != kval)){ //位置中有记录且不等于kval，即有冲突
		Next(p,++c);
	}
	if(H.elem[p].key==kval){
		return p;
	}else{
		return -1;
	}
}

int InsertHash(HashTable &H,ElemType e){
	int c=0,j=0;
	if(HashSearch(H,e.key,j,c)!=-1){
		return -1;
	}else{
		H.elem[j]=e;
		++H.count;
		return 1;
	}
}

未完待续~