一、順序查找
直接遍歷線性表或設定監視哨進行順序查找，
int Search(int a[],int key,int length)
{
int i;
a[0]=key;//監視哨
for(i=length;a[i]!=key;i--);
return i;
}
時間復雜度：O(n)
設定監視哨，免去查找程序中每一步都要檢測表是否查找完畢，雖然時間復雜度與直接遍歷一樣均為O(n)，然而實踐證明，當length>=1000時，這個改進能使順序表進行一次查找所需的平均時間幾乎減少一半，
二、折半查找
又稱二分法，效率較高，但要求線性表必須采用順序存盤結構且有序排列,而且不適用于資料元素經常變動的線性表，
//二分非遞回演算法
int Search1(int a[], int key, int length)
{
int L = 0, R = length - 1, mid;
while (L <= R)
{
mid = (L + R) / 2;
if (a[mid] == key)
{
return mid;
}
else if (key < a[mid])
{
R = mid - 1;
}
else
{
L = mid + 1;
}
}
return 0;
}
//二分遞回演算法
int Search2(int a[], int key, int L, int R)
{
int mid;
if (L > R)
{
return 0;
}
mid = (L + R) / 2;
if (a[mid] == key)
{
return mid;
}
else if (key < a[mid])
{
return Search2(a, key, L, mid - 1);
}
else
{
return Search2(a, key, mid + 1, R);
}
}
時間復雜度：O(log2n)
三、分塊查找
又稱索引順序查找，效率介于分塊查找和折半查找之間，尚需額外建立一個索引表（空間換時間)，塊間有序，塊內無序，
1.建立索引表，索引表按照各個塊中關鍵字大小排序，記錄各個塊的起始位置，
2.確定待查值在哪一塊（折半查找或順序查找），
3.在確定的塊中查找待查找值（順序查找），
優點：不要求線性表有序，也不需要對線性表進行全部遍歷
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275082.html
標籤：其他
上一篇：【C語言學習筆記——3】