線性搜索

procedurelinearsearch(x:整數,a1,a2,...,an:不同整數)

i:=1

while(i<=n&&x=/(不等於)ai)

i:=i+1

ifi<=nthenlocation:=i

elselocation:=0

{location是等於x的下標,或是0(找不到)}

最壞情況下使用O(n)次比較,2分搜索算法最壞情形複雜度O(logn)次比較,2分搜索算法比之線性搜索最壞情況下要好.

int seqsearch(int list[], int searchnum, int n)

{

int i;

list[n] = searchnum; //把搜索值放到最後一個位置，簡化代碼

for(i = 0; list[i] != searchnum; i++)

;

return ((i < n ) ? i : -1);

} 咱們考慮一個最基本的優化方法，就是把訪問到的數據和第一個數據互換。

int seqsearch(int list[], int searchnum, int n)

{

int i;

int ret = -1;

list[n] = searchnum; //把搜索值放到最後一個位置，簡化代碼

for(i = 0; list[i] != searchnum; i++)

;

if(i == 0) {

return 0;

}

if(i<n) {

int temp = list[0];

list[0] = list[i];

list[i] = temp;

ret = 0;

}

return ret;

}

這段代碼把搜索到的記錄和第一個記錄互換，如果同一個記錄連續被訪問，那麼只用做一次比較，提高了性能。但如果兩個記錄交互被訪問，如1 2 1 2 1 2……，那麼性能就會下降了。我們來看一個模擬LRU的代碼：

int seqsearch(int list[], int searchnum, int n)

{

int i;

int ret = -1;

list[n] = searchnum; //把搜索值放到最後一個位置，簡化代碼

for(i = 0; list[i] != searchnum; i++)

;

if(i==0)

return 0;

if(i<n) {

int temp = list[i];

int j;

for(j =i; j>0; j--)

list[j] = list[j-1];

list[0] = temp;

ret = 0;

}

return ret;

}