数组两种查找算法集合

‘壹’ 求查找算法（折半查找法，顺序查找法，分别在一个程序里）“动画演示”程序源代码，一共两个源代码

折半搜索（英语：half-interval search），也称二分搜索（英语：binary search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。

函数实现如下：

bin_search(intA[],intn,intkey){
intlow,high,mid;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(A[mid]==key)returnmid;
if(A[mid]<key){
low=mid+1;
}
if(A[mid]>key){
high=mid-1;
}
}
return-1;
}
C语言实现代码
#include<stdio.h>intmain()
{
inta[11]={0,1,2,3,4,5,6,7,8,9,10},min=0,max=10,mid,n;//max为数列长度，a[0]作为第一个数组元素
printf("请输入您要查找的数:
");
scanf("%d",&n);
while(min+1!=max)
{
mid=(min+max)/2;
if(n>a[mid])min=mid;
elseif(n<a[mid])max=mid;
else
{
printf("输入的数在数列的第%d位
",mid);
exit(0);
}
}
if(n==a[max])
{
max+=1;
printf("
输入的数在数列的第%d位
",max);
}
elseif(n==a[min])
{
min+=1;
printf("
输入的数在数列的第%d位
",min);
}
elseif(n!=a[mid])
printf("
输入的数不在数列中");
}
Dev-c++实现
#include<stdio.h>
#include<stdlib.h>
voidmain()
{
inta[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,15};
intn,m,top,bot,mid;
top=m=1;//此处修改top=0;m=1;
bot=14;
printf("pleaseinputanumber:");
scanf("%d",&n);
while(top<=bot)
{
mid=(top+bot)/2;
if(n==a[mid])
{
printf("这是第%d个元素的值。
",mid+1);
m=0;
break;
}
elseif(n>a[mid])
top=mid+1;
elseif(n<a[mid])
bot=mid-1;
}
if(m)
printf("无此数。
");
system("PAUSE");
return0;
}

顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。

对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，直到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。

函数实现如下：

intsq_search(keytypekeyp[],intn,keytypekey)
{
inti;
for(i=0;i<n;i++)
if(key[i]==key)
returni;//查找成功
return-1;//查找失败
}

上面只是算法实现函数，对于动画部分，自己用moveto，lineto描点划线的方式实现吧。

‘贰’ 二分查找算法

二分查找算法，该算法要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。如果一个序列是无序的或者是链表，那么该序列就不能使用二分查找。

二分查找算法原理：若待查序列为空，则返回-1，并退出算法；若待查序列不为空，则将它的中间元素与目标数值进行比较，判断是否相等；若相等，则返回中间元素索引，并退出算法；此时已查找成功。若不相等，则比较中间元素与目标数值的大小。

二分查找的一个技巧是：不要出现else，而是把所有情况用else，if写清楚，这样可以清楚地展现所有细节。本文都会使用else，if，旨在讲清楚，读者理解后可自行简化。

‘叁’ 几种常见的查找算法之比较

二分法平均查找效率是O(logn)，但是需要数组是排序的。如果没有排过序，就只好先用O（nlogn)的预处理为它排个序了。而且它的插入比较困难，经常需要移动整个数组，所以动态的情况下比较慢。

哈希查找理想的插入和查找效率是O(1)，但条件是需要找到一个良好的散列函数，使得分配较为平均。另外，哈希表需要较大的空间，至少要比O(n)大几倍，否则产生冲突的概率很高。

二叉排序树查找也是O(logn)的，关键是插入值时需要做一些处理使得它较为平衡（否则容易出现轻重的不平衡，查找效率最坏会降到O(n)），而且写起来稍微麻烦一些，具体的算法你可以随便找一本介绍数据结构的书看看。当然，如果你用的是c语言，直接利用它的库类型map、multimap就可以了,它是用红黑树实现的，理论上插入、查找时间都是O(logn)，很方便，不过一般会比自己实现的二叉平衡树稍微慢一些。