一、靜态查找：
隻是起查詢或檢索的作用，不涉及插入、删除，反之為動态查找。
二、順序查找
順序查找過程中往往設定監視哨，在查找過程中不用每一步都檢查整個表是否查找完畢。
假設，每個元素的查找機率相同，順序查找成功時平均查找長度為：(n+1)/2；順序查找不成功時平均查找長度為：(n+1)/4。
考慮到查找不成功的情況，順序查找表的平均查找長度為：3(n+1)/4。
順序查找的優點為：算法簡單，适應面廣，對表結構無任何要求；
缺點為：平均查找長度大，查找效率低。
三、折半查找法
首先折半查找需要求表為有序表，且折半查找可以描述為一棵二叉分類平衡樹。如此看來，查找過程隻是走了一條從根節點到某個結點的路徑。又因為具有n個結點的判定樹深度為：
。是以，查找成功時比較次數最多為：
折半查找的平均查找長度推理如下：
對順序查找和折半查找的實作如下：
staticSearch.h
template<typename T>
int getArrayLength(T &array) {
return (sizeof(array)/sizeof(array[0]));
}
typedef struct LinearList {
ElemType *elem;
int length;
}List;
bool initLinearList(List &L,ElemType b[],int len){
L.elem = (ElemType *)malloc(INIT_LISTSIZE*sizeof(ElemType));
if (L.elem==NULL)
{
cout << "記憶體配置設定失敗！" << endl;
exit(OVERFLOW);
}
L.length = 0;
for (int i = 1; i <= len; i++)
{
L.elem[i] = b[i - 1];
++L.length;
}
return true;
}
//順序查找,傳回所查找元素的位置
Status sqSearch(List &L, ElemType key, int len) {
L.elem[0] = key;
int j;
for (j = len; L.elem[j] != key; j--);
return j;
}
//折半查找
Status binarySearch(List &L, ElemType key, int len) {
int low = 1, high = len;
while (low<=high)
{
int mid = (low + high) / 2;
if (L.elem[mid] == key){
return mid;
}
else
{
if (key < L.elem[mid])
high = mid - 1;
else
low = mid + 1;
}
}
}
主函數search.cpp
int main()
{
int len;
ElemType b[] = {1,4,7,11,23,52,56,65,73,89};
List list1;
len = getArrayLength(b);
cout << "查找數組為：";
for (int i = 0; i < len; i++)
{
visit(b[i]);
}
cout << endl;
initLinearList(list1,b,len);
cout <<"順序查找b[6]的位置為："<< sqSearch(list1,b[6],len)<<endl;
cout << "折半查找b[2]的位置為："<<binarySearch(list1, b[2], len) << endl;
system("pause");
return 0;
}
執行結果如下：