第九章 搜索算法

9.1 顺序搜索

????????顺序或线性搜索是最基本的搜索算法。它的机制是，将每一个数据结构中的元素和我们要找
的元素做比较。顺序搜索是最低效的一种搜索算法。
????????以下是其实现：

Array.prototype.sequentialSearch = function(item){
    for(var i=0;i<this.length;i++){
        if(item === this[i])
        return i  
    }
    return -1
}

????????顺序搜索迭代整个数组，并将每个数组元素和搜索项作比较。如果搜索到了，算法将用返回值来标示搜索成功。返回值可以是该搜索项本身，或是true，又或是搜索项的索引。如果没有找到该项，则返回-1，表示该索引不存在；也可以考虑返回false或者null。
????????假定有数组[5, 4, 3, 2, 1]和待搜索值3，下图展示了顺序搜索的示意图：

9.2 二分搜索

????????二分搜索算法的原理和猜数字游戏类似，就是那个有人说“我正想着一个1到100的数字”的
游戏。我们每回应一个数字，那个人就会说这个数字是高了、低了还是对了。

这个算法要求被搜索的数据结构已排序。以下是该算法遵循的步骤。
(1) 选择数组的中间值。
(2) 如果选中值是待搜索值，那么算法执行完毕（值找到了）。
(3) 如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找。
(4) 如果待搜索值比选中值要大，则返回步骤1并在选种值右边的子数组中寻找。

Array.prototype.binarySearch = function(item){
    this.sort()
    
    var low=0,
    high = this.length-1,
    mid,element

    while(low<=high){
        mid = Math.floor((low+high)/2)
        element = this[mid]
        if(element<item){
            low = mid+1
        }else if(element>item){
            high=mid-1
        }else{
            return mid
        }
    }
    return -1
}

????????开始前需要先将数组排序，我们可以选择任何一个我们之前已经实现的排序算法。在数组排序之后，我们设置low和high指针（它们是边界）。
????????当low比high小时（行{4}），我们计算得到中间项索引并取得中间项的值，此处如果low比
high大，则意思是该待搜索值不存在并返回-1。接着，我们比较选中项的值和搜索值。如果小了，则选择数组低半边并重新开始。如果选中项的值比搜索值大了，则选择数组高半边并重新开始。若两者都是不是，则意味着选中项的值和搜索值相等，因此，直接返回该索引。
????????给定下图所示数组，让我们试试看搜索2。这些是算法将会执行的步骤：