第九章 搜索算法

2023-12-16 23:27:18

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。这些是算法将会执行的步骤:

文章来源:https://blog.csdn.net/weixin_52878347/article/details/135022958
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。