查找算法--顺序表查找

    查找又称检索，是指在某种数据结构中找出满足给定条件的元素。若在查找的同时对表做修改运算(如插入删除），则相应的表称为动态查找表，否则，称为静态查找表。我们分别从线性表查找，树表查找和哈希表查找来分析总结查找算法。

 

线性表查找

 线性表是最简单的一种表的组织方式，我们不考虑在查找的同时对表做修改，即在静态表上进行查找

1）顺序查找

基本思路：

      从表中一端开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至顺序扫描结束，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功

 

基本代码：

 

int SeqSearch(int a[],int len,int key)
{
       int i
       for( i=0;i<len;i++)
       {
            if(a[i]==key)
                break;
       }
       if(i<len)
           return i;//查找成功，返回下标
       else
          return -1;//查找失败，返回-1
}

 特点：

 

   顺序查找成功时的查找平均长度为(n+1)/2，即为表长的一半，查找不成功的查找长度为n，顺序查找的优点是算法简单，且对表的结构没有任何要求。缺点就是查找效率低，当n较大时不宜采用顺序查找。

 

2）二分查找(折半查找)

基本思路：

           将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

基本代码：

    

int BinSearch(int a[],int len,int key)
{
	int low=0,high=len-1,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(a[mid]==key)//查找成功
			return mid;
		else if(a[mid]>key)
			high=mid-1;
		else
			low=mid+1;

	}
	return -1;//查找失败
}

 

 

特点：

      二分查找成功时的平均查找长度为：log2(n+1)-1 。二分查找虽然高效，但是要将表按关键字排序，而排序本身就是一种很费时的运算。二分查找必须采用顺序存储结构，为保表的有序性，在顺序表中插入或删除都必将移动大量数据。因此，二分查找特别适合用于那种一建立就很少改动，而又经常需要查找的线性表

 

 

3）分块查找(索引顺序查找)

基本思想

      分块查找是一种介于顺序查找和二分查找之间的查找方式。查找时，首先查找索引表，因为索引表是有顺序的表，故可二分查找或顺序查找确定待查的记录在哪一块；然后在确定的块中进行顺序查找(因为块内无序，只能顺序查找)

 

结构展示：

 基本代码

    int Search_Index(SSTable &ST,IndexTable &ID,int k)  
    {  
        int low,high,mid;  
        int p;//p用来保存查找的关键字所属的索引中的位置  
        int s,t;//s,t分别用来保存查找的关键字所在块的起始和终点位置  
        low=0;  
        high=ID.length-1;  
        while(low<=high && p<0)  
        {//该循环是用对半查找的方法，对索引表进行查找，从而定位要查找的元素所在的块  
            mid=(low+high)/2;  
            if(k>ID.elem[mid-1].key && k<ID.elem[mid].key)  
                p=mid;//判断关键字对应哪个索引位置，就是k比前一个值大，比后一个值小，  
                        //那个大的就是k对应的索引位置  
            else  
            {  
                if(k<ID.elem[mid].key)  
                    high=mid-1;  
                else if(k>ID.elem[mid].key)  
                    low=mid+1;  
                else  
                    p=mid;  
            }  
        }  
        s=ID.elem[p].stadr;  
        if(p==ID.length-1)  
            t=ST.length;//这里对p的判断很重要，p若是索引中最后一个位置，则t应该为ST的表长  
        else  
            t=ID.elem[p+1].stadr-1;  
        while(k!=ST.r[s]&&s<=t)//这里在块里进行顺序查找  
            s++;  
        if(s>t)  
            return 0;  
        else  
            return s;  
    }  
 

 

 

特点：

       分块查找实际上是两次查找过程，分块查找的效率结余顺序查找和二分查找之间。分块查找的优点是，在表中插入或删除一个记录时，只要找到记录所属的块，就在该块内进行插入和删除运算。因为块内数据存放是无序的，所以无需移动大量记录。分块查找主要代价(缺点)是要增加一个辅助数组的存储空间和将初始表分块排序的运算。

 

总结

      当用线性表作为表组织形式时，其中以二分查找效率最高。但由于二分查找要求表中记录有序，且不能以链表形式存储，因此，在标的插入和删除操作频繁时，为维护标的有序性，需要移动大量记录。这些大量的移动引起的额外时间开销就抵消了二分查找的优点了。所以二分查找只适用于静态表查找。若要对动态表进行高效查找，可用树表查找，下片博客将介绍树表查找。