線性搜尋

比如說我有數組data,1000個元素，要從裡面找x，線性搜尋，就是從頭找到尾，依次來看data[0]是否等於x，如果不是data[1]，data[2],依次類推，一直找到最後一個。速度最慢，但是適用性最廣。

算法步驟

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;

}