数据结构顺序查找

对顺序查找法、二分查找法和分块查找做系统学习。用的书是严老师(严薇敏)的C语言版，使用scala重新编写了一下。语法稍微不同思路是一样的。

顺序查找

说起顺序查找，大家肯定都觉得再熟悉不过了，不过这里面还是有一些需要注意的,假如以前你一直写无哨兵的顺序查找，那你就out了,因为带哨兵的顺序查找能为你省掉将近一半的时间;下面是对两种实现方法以及原理进行说明。

无哨兵

def search(arr : Array[Int] ,elem : Int):Int = {
    var index = -1;
    for ((x,i) <- arr.view.zipWithIndex)
        if(x == elem) index = i
    index
}

思路很清晰，遍历所有数据一个一个比,如果发现匹配就返回对应下标。

有哨兵

def searchSentry(arr : Array[Int] ,elem : Int,n : Int):Int = {
    var i = 0
    if(arr(n) != elem)
        arr(n) = elem
    else
        return n
    while(arr(i) != elem)
        i += 1
    if(i < n) return i else return -1
}

带哨兵的乍一看貌似与无哨兵的没什么区别，然而实践证明，这个改进在length大于1000时，进行查询的时间会减少将近一半。原理是通过监视哨，省去了每次遍历都去检测是否查询完毕的时间。

时间复杂度计算

平均查找长度的计算公式

$$ASL=\sum_{i=1}^n\ P_iC_i$$

从顺序表的查找过程可见，$$C_i$$取决于元素在表中的位置，假如查找第一个记录时，只需要查一次，第n个记录时则需要查n次。

这边假设每个元素查找概率相等，则

$$P_i=\frac{1}{n}$$

继续推导

$$ASL=\frac{1}{n}\sum_{i=1}^n\ i=\frac{1+n}{2}$$

则顺序查找的平均算法复杂度为$$\omicron \left( n \right)$$

如果有疑惑可以看Data Structure (2nd Edition) 7.2.1http://book.knowsky.com/book_1030305.htm

二分查找看下一篇