概念

算法步骤

实例

概念

比如说我有数组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;

}