毕业论文设计--学年论文几种查找算法的比较与总结.doc

学 年 论 文
题 目： 几种查找算法的比较与总结
学 院： 计算机科学与工程
专 业： 计算机科学与技术
班 级: 12级计师1班
学生姓名： 马有华
学 号： 201271030132
指导教师： 曹素珍

I

摘 要
查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中,查找是常用的基本运算。文中介绍四种查找算法．分别是顺序查找、二分查找、二叉排序树查找和哈希查找。并用JAVA语言编写了相应程序代码，比较了查找同一个数据的时间复杂度和空间复杂度。

关键词: 查找算法；时间复杂度；空间复杂度

Abstract

Searching is a commonly basic operation that can find a number of information in computer applications.In this paper,four tapyes of searching algorithm are introduced.They are squential earch,binary search tree,and bash search.The progarm’s codes based on java are complied. The time complexity and space complexity to look for the same data and compared.

Key words: Searching Algorithm；Timecomplexity；Spacecomplexity

目 录
摘 要 1
1 算法概述 1
1.1引言 1
1.2顺序查找 2
1.3二分查找 2
1.3.1二分查找要求 2
1.3.2优缺点 2
1.3.3算法思想 2
1.3.4算法复杂度 3
1.4分块查找 3
1.4.1方法描述 3
1.4.2操作步骤 3
1.5哈希表查找 4
1.5.1基本原理 4
1.5.2函数构造 4
1.5.3冲突处理 4
1.5.4支持运算 4
2 算法实现 7
2.1顺序查找 7
2.1.1方法分类 7
2.2二分查找 8
2.2.1算法要求 8
2.2.2算法复杂度 8
2.2.3代码示例 9
2.2.4递归实现 11
2.3分块查找 16
2.3.1方法描述 16
2.3.2操作步骤 17
2.4哈希表查找 18
2.4.1操作步骤 18
2.4.2解决冲突 19
3 比较与总结 22
3.1分类查找的依据 22
3.2效率比较 22
参考文献 24

26

1 算法概述
1.1引言
用关键字标识一个数据元素，查找时根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。
顺序查找也称为线形查找，从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
二分查找要求线形表中的结点按关键字值升序或降序排列，用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
分块查找也称为索引查找，把线形分成若干块，在每一块中的数据元素的存储顺序是任意的，但要求块与块之间须按关键字值的大小有序排列，还要建立一个按关键字值递增顺序排列的索引表，索引表中的一项对应线形表中的一块，索引项包括两个内容：1）键域存放相应块的最大关键字；2）链域存放指向本块第一个结点的指针。分块查找分两步进行，先确定待查找的结点属于哪一块，然后在块内查找结点。
哈希表查找是通过对记录的关键字值进行运算，直接求出结点的地址，是关键字到地址的直接转换方法，不用反复比较。假设f包含n个结点，Ri为其中某个结点（1≤i≤n），keyi是其关键字值，在keyi与Ri的地址之间建立某种函数关系，可以通过这个函数把关键字值转换成相应结点的地址，有：addr(Ri)=H(keyi)，addr(Ri)为哈希函数。
1.2顺序查找
顺序查找过程：从表中的最后一个记录开始，逐个进行记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功，找到所查的记录；反之，若直到第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查的记录，查找失败。
算法描述为：
　　int Search(int d,int a[],int n)
　 　{　　
/*在数组a[]中查找等于D元素，若找到，则函数返回d在数组中的位置，否则为0。其中n为数组长度*/
int i ；
　　 /*从后往前查找*/
for(i=n-1;a!=d;--i) 此处程序正确吗？
return i ；
　 　/*如果找不到，则i为0*/
　　}
1.3二分查找
二分查找又称折半查找，它是一种效率较高的查找方法。
1.3.1二分查找要求
1）必 须采用顺序存储结构。
2）必须按关键字大小有序排列。
1.3.2优缺点
折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
1.3.3算法思想
首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此 时查找不成功。
1.3.4算法复杂度
假设其数组长度为n，其算法复杂度为O(log(n))，下面提供一段二分查找实现的伪代码:

BinarySearch(max,min,des)
mid-des then 此处程序正确吗？
　 max=mid-1
　 else
min=mid+1
return max
折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果xa[n/2]，则我们只要在数组a的右 半部继续搜索x。
1.4分块查找
step1 先选取各块中的最大关键字构成一个索引表。step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。
1.4.1方法描述
将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不 必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……
1.4.2操作步骤
step1 先选取各块中的最大关键字构成一个索引表。step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。
1.5哈希表查找
1.5.1基本原理
从此处开始至正文最后一页的文字部分格式，按照如下格式设置：
字体：正文宋体；字号：小四；段落中的格式为：正文：两端对齐；首行缩进：2字符；间距：段前段后均为：0行；行距：1.5倍行距。具体图示如下：

代码部分请仔细检查正误。然后按照上述正文设置格式以及代码缩进格式调整。
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。
1.5.2函数构造
构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：
1) 除余法
选择一个适当的正整数 p ，令 h(k ) = k mod p
　　这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。
2) 数字选择法
如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。
1.5.3冲突处理
线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。
1.5.4支持运算
哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。
　　设插入的元素的关键字为 x ，A 为存储的数组。
　　初始化比较容易，例如
　　const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素
　　p=9997; // 表的大小
　　procedure makenull;
　　var i:integer;
　　begin
　　for i:=0 to p-1 do
　　A:=empty;
　　End;
哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：
　 　function h(x:longint):Integer;
　　 begin
　　 h:= x mod p;
　　 end;
我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 locate
　　function locate(x:longint):integer;
　　var orig,i:integer;
　　begin
　　orig:=h(x);
　　i:=0;
　　while (ix)and(A[(orig+i)mod S]empty) do
　　inc(i);
　　//当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元
　　//素存储的单元，要么表已经满了
　　 locate:=(orig+i) mod S;
　　 end;
　　插入元素
　 　procedure insert(x:longint);
　　 var posi:integer;
　 　begin
　　 posi:=locate(x); //定位函数的返回值
　　 if A[posi]=empty then A[posi]:=x
　　 else error; //error 即为发生了错误，当然这是可以避免的
　　 end;
查找元素是否已经在表中
　 　procedure member(x:longint):boolean;
　 　var posi:integer;
　 　begin
　 　posi:=locate(x);
　 　if A[posi]=x then member:=true
　 　else member:=false;
　　 end;

2 算法实现
2.1顺序查找
在一个已知无(或有序）序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。
2.1.1方法分类
(1）Java实现方法
package search;
/*顺序查找
* des 要查找的元素
* i 保存当前元素的下标
*/
public class OrderSearch {
public static int ordersearch(int[] arry,int des){
int i=0;
for(;i<=arry.length-1;i++){
if(des==arry[i])
return i;
}
return -1;
}
public static void main(String[] args){
int[] a=new int[]{2,3,5,6,7,3,};
System.out.println(ordersearch(a,3));
}
}
(2) C实现算法
int sq_search(keytype keyp[],int n,keytype key)
{
int i;
for(i=0; ifor( i=0;i找
2.2.1算法要求
1） 必须采用顺序存储结构
2）必须按关键字大小有序排列。
2.2.2算法复杂度
假设其数组长度为n，其算法复杂度为o（log（n））
下面提供一段二分查找实现的伪代码:
BinarySearch(max,min,des)
mid-<(max+min)/2
while(min<=max)
mid=(min+max)/2
if mid=des then
return mid
elseif mid >des then
max=mid-1
else
min=mid+1
return max
折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果xa[n/2]，则我们只要在数组a的右 半部继续搜索x。

2.2.3代码示例
1）Python源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def binarySearch(lists,select):
    is_none=False
    iflists!=[]:
    cen_num=len(lists)/2
    tlag=lists[cen_num]
    gt_list=lists[0:cen_num]
    lt_list=lists[cen_num+1:]

if tlag==select:
    is_none=True
    return is_none
elif tlag>select:
    is_se=binarySearch(gt_list,select)
    if notis_se:
        return binarySearch(lt_list,select)
    return is_none
    elif tlag
26
programjjzx(input,output);
var
a:array[1..10]ofinteger;
i,j,n,x:integer;
begin
['输入10个从小到大的数：']
fori:=1to10doread(a[i]);
['输入要查找的数：']
readln(x);
i:=1;n:=10;j:=trunc((i+n)/2);
repeat
ifa[j]>xthen
begin
n:=j-1;j:=trunc((i+n)/2)
end
elseifa[j]
end;
until(a[j]=x)or(i>=n);{为什么是这个结束循环条件}
ifa[j]=xthen
writeln('查找成功！位置是：',j:3)
else
writeln('查找失败，数组中无此元素！')
end.
PHP代码实现
3）C语言代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

43
44
45

intBinSearch(SeqList*R，intn,KeyTypeK)
{
//在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回-1
intlow=0，high=n-1，mid；//置当前查找区间上、下界的初值
while(low<=high)
{
if(R[low].key==K)
returnlow;
if(R[high].key==k)
returnhigh;
//当前查找区间R[low..high]非空
mid=low+((high-low)/2)；
//使用(low+high)/2会有整数溢出的问题
//（问题会出现在当low+high的结果大于表达式结果类型所能表示的最大值时，
//产生溢出后再/2是不会产生正确结果的，而low+((high-low)/2)不存在这个问题
if(R[mid].key==K)
returnmid；//查找成功返回
if(R[mid].keyhigh)
return-1；//当low>high时表示所查找区间内没有结果，查找失败
}//BinSeareh

------------上面代码复杂难懂-----------------
intbsearchWithoutRecursion(intarray[],intlow,inthigh,inttarget)
{
while(low<=high)
{
intmid=(low+high)/2;
if(array[mid]>target)
high=mid-1;
elseif(array[mid]et
return-1;
}
----------------------------------------
2.2.4递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
intbinary_search(constintarr[],intlow,inthigh,intkey)
{
intmid=low+(high-low)/2;
if(low>high)
return-1;
else{
if(arr[mid]==key)
returnmid;
elseif(arr[mid]>key)
returnbinary_search(arr,low,mid-1,key);
else
returnbinary_search(arr,mid+1,high,key);
}
}
1）Java代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int binarySearch(Integer[] srcArray, int des) {
    int low = 0;
    int high = srcArray.length - 1;

    while ((low <= high) & (low <= srcArray.length - 1)
            && (high <= srcArray.length - 1)) {
        int middle = low + ((high - low) >> 1);
        if (des == srcArray[middle]) {
            return middle;
        } else if (des < srcArray[middle]) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
    }
    return -1;
}
2）AAuto代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//二分查找
functionbinSearch(t,v){
varp=#t;
varp2;
varb=0;
do{
p2=p;
p=b+math.floor((p-b)/2)//二分折半运算
if(p==b)return;
if(t[p]v)//判断上限
returnt[p]==v&&p;
}
//测试
tab={}
//创建数组，每个元素都是随机数
for(i=1;10;1){
tab[i]=math.random(1,10000)
}
//插入一个已知数
table.push(tab,5632)
//排序
table.sort(tab)
io.open()
io.print("数组",table.tostring(tab))
io.print("使用二分查找，找到5632在位置：",binSearch(tab,5632))
}
3）PHP代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//递归版本
functionbin_sch($array,$low,$high,$k){
if($low<=$high){
$mid=intval(($low+$high)/2);

if($array[$mid]==$k){
return$mid;
}elseif($k<$array[$mid]){
returnbin_sch($array,$low,$mid-1,$k);
}else{
returnbin_sch($array,$mid+1,$high,$k);
}
}
return-1;
}
//非递归版本
functionbinsearch($x,$a){
$c=count($a);
$lower=0;
$high=$c-1;
while($lower<=$high){
$middle=intval(($lower+$high)/2);
if($a[$middle]>$x)
$high=$middle-1;
elseif($a[$middle]<$x)
$lower=$middle+1;
else
return$middle;
}
return-1;
}
4）C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
intbinSearch(constint*Array,intstart,intend,intkey){
intleft,right;
intmid;
left=start;
right=end;
//注释中为递归算法，执行效率低，不推荐
/*
if(keyArray[mid]){
return(binSearch(Array,mid+1,right,key));
}else
returnmid;
*/

while(left<=right){
mid=(left+right)/2;
if(key==Array[mid]){
returnmid;
}
elseif(keyy>Array[mid]){
left=mid+1;
}
}
return-1;
}
[1] 
5）AS3代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
publicstaticfunctionbinSearch(list:Array,low:int,high:int,key:int):int{
if(low>high)
return-1;
varmid:int=low+int((high-low)/2);
varindex:int=-1
if(list[mid]==key){
index=mid;
}elseif(list[mid]<=high){
if(arr[low]==find)
returnlow;
if(arr[high]==find)
returnhigh;
varmid=Math.ceil((high+low)/2);
if(arr[mid]==find){
returnmid;
}elseif(arr[mid]>find){
returnbinary(find,arr,low,mid-1);
}else{
returnbinary(find,arr,mid+1,high);
}
}
return-1;
}
binary(15,Arr,0,Arr.length-1);
7）PHP代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*二分查找：前提，该数组已经是一个有序数组，必须先排序，再查找。*/
functionbinarySearch(&$array,$findVal,$leftIndex,$rightIndex){
$middleIndex=round(($rightIndex+$leftIndex)/2);
if($leftIndex>$rightIndex){
echo'查无此数';
return;
}
if($findVal>$array[$middleIndex]){
binarySearch($array,$findVal,$middleIndex+1,$rightIndex);
}elseif($findVal<$array[$middleIndex]){
binarySearch($array,$findVal,$leftIndex,$middleIndex-1);
}else{
echo"找到数据:index=$middleIndex;value=$array[$middleIndex]";
if($array[$middleIndex+1]==$array[$middleIndex]&&$leftIndex<$rightIndex){
binarySearch($array,$findVal,$middleIndex+1,$rightIndex);
}
if($array[$middleIndex-1]==$array[$middleIndex]&&$leftIndex<$rightIndex){
binarySearch($array,$findVal,$leftIndex,$middleIndex-1);
}
}
}

2.3分块查找
2.3.1方法描述
分块查找要求把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。此外，还要建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找；然后，在相应的块中采用顺序查找，即可找到对应的节点。
分块查找在现实生活中也很常用。例如，一个学校有很多个班级，每个班级有几十个学生。给定一个学生的学号，要求查找这个学生的相关资料。显然，每个班级的学生档案是分开存放的，没有任何两个班级的学生的学号是交叉重叠的，那么最好的查找方法实现确定这个学生所在的班级，然后再在这个学生所在班级的学生档案中查找这个学生的资料。上述查找学生资料的过程，实际上就是一个典型的分块查找。

2.3.2操作步骤
step1 先选取各块中的最大关键字构成一个索引表；[1] 
step2 查找分两个部分：先对索引表进行二分查找,顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。
在C语言中其代码如下：
#include
struct index /*定义块的结构*/
{
int key;
int start;
int end;
} index_table[4]; /*定义结构体数组*/
int block_search(int key, int a[]) /*自定义实现分块查找*/
{
int i, j;
i = 1;
while (i <= 3 && key > index_table[i].key) /*确定在那个块中*/
i++;
if (i > 3) /*大于分得的块数，则返回0*/
return 0;
j = index_table[i].start; /*j等于块范围的起始值*/
while (j <= index_table[i].end && a[j] != key) /*在确定的块内进行查找*/
j++;
if (j > index_table[i].end) /*如果大于块范围的结束值，则说明没有要查找的数,j置0*/
j = 0;
return j;
}
main()
{
int i, j = 0, k, key, a[16];
printf("please input the number:\n");
for (i = 1; i < 16; i++)
scanf("%d", &a[i]); /*输入由小到大的15个数*/
for (i = 1; i <= 3; i++)

{
index_table[i].start = j + 1; /*确定每个块范围的起始值*/
j = j + 1;
index_table[i].end = j + 4; /*确定每个块范围的结束值*/
j = j + 4;
index_table[i].key = a[j]; /*确定每个块范围中元素的最大值*/
}
printf("please input the number which do you want to search:\n");
scanf("%d", &key); /*输入要查询的数值*/
k = block_search(key, a); /*调用