比如说我有数组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
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
int temp = list[i];
int j;
for(j =i; j>0; j--)
list[j] = list[j-1];
list[0] = temp;
ret = 0;
}
return ret;
}