顺序查找

顺序查找（Sequential Search）又叫做线性查找，是基本的查找技术

线性查找的思想

  • 从表开始的第一个或最后一个开始，逐个进行记录的关键字和给与的定值进行比较
  • 若相同，则查找成功
  • 若遍历全表全部不同则查找失败

算法实现

1
2
3
4
5
6
7
8
9
10
/*a为数组，n为查找的数组长度，key为查找的关键字*/

int Sequential Search(int *a,int n,int key){
    int i;
    for(i=1;i<=n;i++){< span>
        if (a[i]==key)
            return i;
    }
    return 0;
}

算法优化

每次循环都会去处理i是否越界，可以使用“驻点”免去i的判断具体代码如下：

1
2
3
4
5
6
7
8
9
int Sequential_Search2(int *a,int n,int key){
    int i;
    a[0]=key;
    i=n;
    while(a[i]!=key){
        i--;
    }
    return i;
}

放置驻点可以在数据量多时免去i的判断提升效率。

算法分析

  • 顺序查找算法有非常大的缺点，查找的效率低下，但是当对于小数据查找时也非常适用
  • 顺序查找最好的时间复杂度即是1，第一个位置就找到
  • 最坏的查找时间复杂度是最后一个位置，为O（n）

算法复杂度