數組兩種查找演算法集合

『壹』 求查找演算法（折半查找法，順序查找法，分別在一個程序里）「動畫演示」程序源代碼，一共兩個源代碼

折半搜索（英語：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)，很方便，不過一般會比自己實現的二叉平衡樹稍微慢一些。