首页 > 代码库 > 查找算法--线性结构的查找方法
查找算法--线性结构的查找方法
查找基本概念：
查找又称为检索，指从一批记录中找出满足指定条件的某一记录过程。在日常生活中比如通讯录查找，字典查找等经常使用查找方法；在程序设计中，查找在许多程序中需要占用很多时间，因此，一个好的查找方法可以提高程序的运行速度。
主关键字和次关键字：
在需要查找的数据结构中，每条记录一般包含多个数据域。查找条件一般是给定其中的一个或几个域的值，这些作为查找条件的域成为关键字（KEY），如果关键字可以唯一标示数据结构中的一条记录，则称此关键字（Primary Key）；若关键字不能唯一区别各个不同的记录，则称此关键字为次关键字（Secondary Key）。最常用，最主要的是以主关键字查找
查找结果
如果通过查找找到与给定关键字相对应的记录，表明查找成功，返回记录的存储位置，以便对记录进行处理（输出，修改，删除等）。找不到与给定关键字对应的记录，表示查找失败，返回一个特定的失败值。
静态查找表和动态查找表
进行查找使用的数据结构称为查找表，可以分为静态查找表和动态查找表：
静态查找表：查找过程中，数据结构不改变的查找称为静态查找表，在静态查找表中，查找失败后，将返回失败值。
动态查找表：查找过程中，数据结构随查找过程进行改变的查找表称为动态查找表，在动态查找表中，查找失败后，将查找表中原来不存在的记录增加到查找表中，另外，动态查找表可以删除指定的关键字的记录。
下面介绍当数据的结构为线性结构时，采用的两种简单的查找方法：顺序查找和折半查找（又叫二分查找）。
1.顺序查找：
顺序查找（Sequential Search）是最简单的一种查找方法，基本思想是：从线性表一端开始，依次将每个记录的关键字与给定值比较，若关键字等于给定值，表示查找成功，返回记录序号，若将线性表中所有记录都比较完，没有找到关键字和给定值相等的记录，查找失败，返回失败值。
例：
#include <stdio.h>#define ARRAYLEN 8 //静态查找表的元素 int source[ARRAYLEN]={69,65,90,37,92,6,28,54}; //静态查找表 int SeqSearch(int s[],int n,int key){ int i; for(i=0;i<n&&s[i]!=key;i++) //循环查找关键字 ; if(i<n) //在静态查找表中找到关键字 return i; else return -1;}int main(){ int key,i,pos; printf("\n请输入关键字:"); scanf("%d",&key); pos=SeqSearch(source,ARRAYLEN,key); printf("原数据:\n"); for(i=0;i<ARRAYLEN;i++) printf("%d ",source[i]); if(pos>=0) printf("\n查找成功，该关键字位于%d个位置:",pos+1); //加1让位置显示从1开始 else printf("\n查找失败!"); return 0;}
在上面顺序查找的循环语句中，每次循环都需要进行两个比较（i<n && r[i]!=key），如果静态查找表中的数据很多，每两次比较需要进行较长时间，这样程序效率比较低，这时可以对SeqSearch算法进行改进，在创建静态查找表中，需要在该表的末端增加一个空的单元，用来保存查找的关键字，这样确保静态查找表中有一个和查找关键字相同的数据，可以去除i<n的判断，每次查找时，查找表中总是能找到关键字，但是若找到第n+1个元素才找到关键字时才找到关键值，表示查找失败。
改进后：
#include <stdio.h>#define ARRAYLEN 8 //静态查找表的元素 int source[ARRAYLEN+1]={69,65,90,37,92,6,28,54}; //静态查找表 int SeqSearch(int s[],int n,int key){ int i; for(i=0;s[i]!=key;i++) //循环查找关键字 ; if(i<n) //在静态查找表中找到关键字 return i; else return -1;}int main(){ int key,i,pos; printf("\n请输入关键字:"); scanf("%d",&key); source[ARRAYLEN]=key; //将key保存到查找表最后 pos=SeqSearch(source,ARRAYLEN,key); printf("原数据:\n"); for(i=0;i<ARRAYLEN;i++) printf("%d ",source[i]); if(pos>=0) printf("\n查找成功，该关键字位于%d的位置:",pos+1); //加1让位置显示从1开始 else printf("查找失败\n"); return 0;}
上述代码第22行将key保存到查找表的最后，key值一个一个与查找表中元素对比，当在第9个元素之前对比成功，则查找成功，当找到第9个位置即key保存的位置，肯定能匹配成功，但是此时是第9个了，表示查找失败。此过程省去了i<n的比较。
顺序查找优点：对静态查找表中的数据的顺序没有要求，当需要创建动态查找表时，可以方便的将查找不成功的数据添加到查找表的末尾。
顺序查找表的缺点：速度慢，在最坏情况下，查找成功需要进行n此比较，查找失败要n+1此比较。
2.折半查找：
折半查找又叫二分查找，这种查找方法要求查找表中数据是线性结构保存，而且查找表中数据是按照关键字有序排列的（从小到大或从大到小）
下面以数据从小到大的n个元素有序排列介绍折半查找过程：
首先是位于查找表中间的位置元素的序号m（m=n/2），取s[m]的关键字与给定值key进行比较，有三种可能：
- 若s[m]=key,表示查找成功。
- 若s[m]>key，表示关键字key在最小值与中间值之间，在前半部分进行折半查找。
- 若s[m]<key，表示关键字key在最大值与中间值之间，在后半部分进行折半查找。
从上面过程看出，折半查找是一种递归的过程，每次折半，都能使查找的范围缩小一半，当查找的范围缩小到只剩下一个元素时，而该元素与关键字不相等，表示查找失败。
在最坏情况下，折半查找所需要的比较次数是O(logn)，查找效率比顺序查找快很多。
比如有这几个数据：6,12,28,37,54,65,69,83,90,92,以37作为关键字，进行查找：
过程：
下面编写程序实现折半查找的过程：
#include<stdio.h>#define ARRAYLEN 10int source[]={6,12,28,37,54,65,69,83,90,92};int BinarySearch(int s[],int n,int key){ int low,height,mid; low=0; height=n-1; while(low<=height) //查找范围 至少包含一个元素 { mid=(low+height)/2; if(s[mid]==key) return mid; //返回序号 else if(s[mid]>key) height=mid-1; else low=mid+1; //定义查找范围 } return -1; //返回查找失败 }int main(){ int key,i,pos; printf("\n请输入要查找的关键字:\n"); scanf("%d",&key); pos=BinarySearch(source,ARRAYLEN,key); printf("原数据："); for(i=0;i<ARRAYLEN;i++) printf("%d ",source[i]); printf("\n"); if(pos>=0) printf("\n查找成功，该关键字位于第%d个位置。\n",pos+1); else printf("查找失败\n"); return 0;}
折半查找的优点是：平均性能好，查找速度快，最多查找次数为O（log（n）），可以快速逼近关键字。
折半查找的缺点是：对查找表中数据排列有要求，首先是顺序排列，而且是有序排列的（从小到大或从大到小），因此使用折半查找时需要先对查找表进行排序；当查找关键字不成功时，如果需要将该关键字添加到查找表中，则需要对已有数据进行大量移动，同样删除也需要移动大量数据。
查找算法--线性结构的查找方法