7.1 顺序表查找

顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或者第一个）记录，其关键字和估计值比较都不等时，则表中没有所查的记录，查找不成功。

具体代码为：

<?php
header("content-type:text/html;charset=utf-8");
/**
 * 顺序查找操作操作
 *
 *包括
 * 1.初始化 __contruct()
 * 2.普通顺序查找 search_none()
 * 3.有哨兵顺序查找 search()

 */
class Sequential_search{
    private $a;
    private $length;

    //初始化
    public function __construct($a = array())
    {
        $this->length = count($a);
        for ($i = 1;$i<=$this->length;$i++){
            $this->a[$i] = $a[$i-1];
        }


    }

    //普通顺序查找
    public function search_none($key){
        for ($i = 1;$i<=$this->length;$i++){
            if($this->a[$i]==$key){
                return $i;
            }
        }
        return 0;
    }

    //有哨兵顺序查找
    public function search($key){
        $this->a[0] =$key;     //设置a[0]为关键字，我们称之为哨兵
        $i = $this->length;   //循环数组从尾部开始
        while ($this->a[$i] !=$key){
            $i--;
        }
        return $i;          //返回0则说明查找失败
    }
}
?>

实现上述函数：

<?php
header("content-type:text/html;charset=utf-8");
include "sequential_search.class.php";

$a = array("小","林","子","奋","斗","的","点","滴");
$sequential_search = new Sequential_search($a);
echo "初始化数组：";
echo "</br>";
print_r($sequential_search);
echo "</br>";
echo "</br>";

$key = $sequential_search->search_none("林");
echo "普通顺序查找“林”在数组中的位置：";
echo "</br>";
echo $key;
echo "</br>";
echo "</br>";

$key = $sequential_search->search("林");
echo "此时数组为：";
echo "</br>";
print_r($sequential_search);
echo "</br>";
echo "</br>";

echo "有哨兵顺序查找“林”在数组中的位置：";
echo "</br>";
echo $key;
?>

最后的实现结果为：

对于顺序查找算法来说，查找成功最好的情况就是在第一个位置就找到了，算法的时间复杂度为O（1），最坏的情况是在最后一个位置才找到，需要n次比较，时间复杂度为O（n），当查找不成功时，需要n+1次比较，时间复杂度为O（n）。关键字在任何位置的概率是相同的，所以平均查找次数是（n+1）/2，所以最终的时间复杂度还是O（n）。