查找算法简介&顺序表查找

　　查找表是同一类型的数据元素构成的集合，根据操作方式，查找表可以分为两类：

　　　　静态查找表：只进行查找操作；

　　　　动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者删除已经存在的数据元素。

　　为了提高查找的效率，我们专门为查找设置了相应的数据结构，称为查找结构。根据查找用到的数据结构，可以将查找分为以下几类：

　　　　表：顺序表查找（顺序查找，有哨兵的顺序查找），有序表查找（二分查找，插值查找，斐波那契查找），哈希表查找；

　　　　索引：稠密索引查找，分块索引查找，倒排索引查找；

　　　　树：二叉排序树查找，平衡二叉树查找。

　　其中，借助于表和索引的查找为静态查找，借助于树的查找为动态查找。

　　顺序查找的查找过程：从表中的第一个或最后一个记录开始，依次将记录的关键字与给定的关键字进行比较，若某个记录的关键字与给定的关键字的值相等，则查找成功，返回该记录在查找表中的位置；否则，查找失败，返回0。

//顺序查找
//a，数组；n，数组长度；key，带查找的关键字
int SequentialSearch(int* a, int n, int key)
{
    for (int i = 1; i <= n; i++)//a[0]不参与查找
    {
        if (a[i] == key)
            return i;//返回key在数组a中的下标
    }
    return 0;//返回0，说明查找失败，否则，查找成功
}

　　上述顺序查找，每次循环都需要进行下标越界的判断，可以将a[0]设置为哨兵，解决需要进行下标越界判断的问题。

//有哨兵的顺序查找
int SequentialSearch2(int* a, int n, int key)
{
    int i = n;//循环从数组的尾部开始
    a[0] = key;//哨兵，存储带查找的关键字的值

    //无论数组中是否存在待查找的关键字
    //最终一定会满足a[i] == key 的条件，因为key存在a[0]中
    while (a[i] != key )
        i--;

    return i;//返回0，说明查找失败，否则，查找成功，返回key在数组a中的下标
}

参考书籍：程杰 著，《大话数据结构》，清华大学出版社。