1、順序查找
時間復雜度：O(n)
優點：算法簡單，對查找表的記錄沒有任何要求
缺點：效率低下
適用：數據量較少時的查找
原理：
在一個已知無(或有序）序隊列中找出與給定關鍵字相同的數的具體位置。原理是讓關鍵字與隊列中的數從最後一個開始逐個比較，直到找出與給定關鍵字相同的數為止。
int SequenceSearch(int *array, int size, int key)
{
int i;
for(i=0; i<size; i++)
{
if(array[i]==key)
{
return i;
}
}
return -1;
}
int SequenceSearch(int *array, int size, int key)
{
int i=size-1;
array[0]=key; //哨兵
while(key != array[i])
{
i--;
}
return i;
}
2、二分查找/折半查找
時間復雜度：O(logn)
優點：比較次數少，查找速度快，平均性能好；
缺點：要求待查表為有序表，且插入刪除困難。
適用：折半查找方法適用於不經常變動而查找頻繁的有序列表。
原理：
首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
int BinarySearch(int *array, int size, int key)
{
int first,last,middle;
first=0;
last =size;
while(first<=last)
{
middle = (first+last)/2;
if(array[middle] < key)
first=middle+1;
else if(array[middle] > key)
last=middle-1;
else
return middle;
}
return -1;
}
3、插值查找
時間復雜度：O(logn)適用：數據量較大，而關鍵字分布又比較均勻的查找表
原理：
英漢字典中尋找單詞“worst”，我們決不會仿照對半查找那樣，先查找字典中間的元素，然後查找字典四分之三處的元素等等. 事實上，我們是在所期望的地址(在字典的很靠後的地方)附近開始查找的。
int InsertSearch(int *array, int size, int key)
{
int first,last,position;
first=0;
last =size-1;
while(first<=last)
{
position = first+ (last-first)*(key-array[first])/(array[last]-array[first]);
if(array[position] < key)
first=position+1;
else if(array[position] > key)
last=position-1;
else
return position;
}
return -1;
}
4、斐波那契查找
時間復雜度：O(logn)
原理：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int F[100];
int FibonacciSearch(int *a,int n,int key)
{
int low,high,mid,i,k=0;
low=1; /* 定義最低下標為記錄首位 */
high=n; /* 定義最高下標為記錄末位 */
while(n>F[k]-1)
k++;
for (i=n;i<F[k]-1;i++)
a[i]=a[n];
while(low<=high)
{
mid=low+F[k-1]-1;
if (key<a[mid])
{
high=mid-1;
k=k-1;
}
else if (key>a[mid])
{
low=mid+1;
k=k-2;
}
else
{
if (mid<=n)
return mid; /* 若相等則說明mid即為查找到的位置 */
else
return n;
}
}
return -1;
}
int main()
{
int i;
int arr[]={0,1,16,24,35,47,59,62,73,88,99};
F[0]=0;
F[1]=1;
for(i = 2;i < 100;i++)
{
F[i] = F[i-1] + F[i-2];
}
printf("%d\n", FibonacciSearch(arr,sizeof(arr)/sizeof(int)-1,99));
return 0;
}
5、哈希查找
時間復雜度：O(1)
適用：數據本身是無法排序、無法比較
原理：
通過記錄數據元素與存儲地址的關系，直接定位數據元素的一種方法。
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存儲空間初始分配量 */
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 /* 定義散列表長為數組的長度 */
#define NULLKEY -32768
typedef int Status; /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */
typedef struct
{
int *elem; /* 數據元素存儲基址，動態分配數組 */
int count; /* 當前數據元素個數 */
}HashTable;
int m=0; /* 散列表表長，全局變量 */
/* 初始化散列表 */
Status InitHashTable(HashTable *H)
{
int i;
m=HASHSIZE;
H->count=m;
H->elem=(int *)malloc(m*sizeof(int));
for(i=0;i<m;i++)
H->elem[i]=NULLKEY;
return OK;
}
/* 散列函數 */
int Hash(int key)
{
return key % m; /* 除留余數法 */
}
/* 插入關鍵字進散列表 */
void InsertHash(HashTable *H,int key)
{
int addr = Hash(key); /* 求散列地址 */
while (H->elem[addr] != NULLKEY) /* 如果不為空，則沖突 */
{
addr = (addr+1) % m; /* 開放定址法的線性探測 */
}
H->elem[addr] = key; /* 直到有空位後插入關鍵字 */
}
/* 散列表查找關鍵字 */
Status SearchHash(HashTable H,int key,int *addr)
{
*addr = Hash(key); /* 求散列地址 */
while(H.elem[*addr] != key) /* 如果不為空，則沖突 */
{
*addr = (*addr+1) % m; /* 開放定址法的線性探測 */
if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) /* 如果循環回到原點 */
return UNSUCCESS; /* 則說明關鍵字不存在 */
}
return SUCCESS;
}
int main()
{
int arr[HASHSIZE]={12,67,56,16,25,37,22,29,15,47,48,34};
int i,p,key,result;
HashTable H;
key=39;
InitHashTable(&H);
for(i=0;i<m;i++)
InsertHash(&H,arr[i]);
result=SearchHash(H,key,&p);
if (result)
printf("查找 %d 的地址為：%d \n",key,p);
else
printf("查找 %d 失敗。\n",key);
for(i=0;i<m;i++)
{
key=arr[i];
SearchHash(H,key,&p);
printf("查找 %d 的地址為：%d \n",key,p);
}
return 0;
}
