1  顺序查找

顺序查找又称线性查找，是最基本的查找方法之一。它以顺序表或线性链表表示静态查找表。其查找方法为：从表的最后一个记录开始，逐个按给定值与关键字进行比较，若找到，查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与给定值相同的关键字，则查找失败。

 

【算法8.1】数据元素从下标为1的数组单元开始存放，0号单元留空。

int  s_search(SSTable  tbl，KeyType  k)

{        //在表tbl中查找关键码为k的数据元素，若找到返回该元素在数组中的下标，否则返回0

    tbl.elem[0].key = k; 

//存放监测，这样在从后向前查找失败时，不必判表是否检测完,从而达到算法统一\

    for( i = tbl.length ; tbl.elem[i].key != k ；i-- );       //从表尾端向前找\

    return  i；

} 

顺序查找缺点是当n很大时，平均查找长度较大，效率低；优点是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。

2  折半查找

折半查找又称二分查找（Binary Search），是一种查找效率较高的查找方法。折半查找对待查的线性表有两个要求：

（1）必须采取顺序存储结构；

（2）必须按关键字大小排序的有序表。

其查找基本思想为：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。