javascript数据结构与算法——搜索算法

TZLLOG 发布于2019-08-22 18:19 / 1156人阅读

摘要：前言本书当中说了两种搜索算法，篇幅都不大，因为融合了之前的知识点，所以看起来会相对简单一，主要包括两个内容顺序搜索二分搜索顺序搜索从字面的意思来看，就是按照顺序一个一个找下去的意思，直到找到为止。该搜索算法要求被搜索的数据结构已排序。

前言

本书当中说了两种搜索算法，篇幅都不大，因为融合了之前的知识点，所以看起来会相对简单一，主要包括两个内容：

顺序搜索

二分搜索

顺序搜索

从字面的意思来看，就是按照顺序一个一个找下去的意思，直到找到为止。搜索的结果可以返回true、当前索引、当前值，否则返回false,-1,null等内容，我们看如下一段代码：

    var sequentialSearch = function(item){
        for (var i = 0;i
  整体的思路就是遍历数据，然后把遍历到的每项内容，跟我们要查找的元素相比较，如果值相等就遍历结束，使用 return 返回，否则在遍历结束的时候返回其它内容。
假定有如下数组，我们要在里面查找值为3的元素项：
[5,4,3,2,1]
搜索的示意图如下：

二分搜索
  所谓的二分，就是把数据一分为二，首先选中一个中间值，如果中间值是需要查找的，那么返回该值，否则拿需要查找的值跟这个中间值比较，然后依次循环执行这个步骤，直到找到为止。
    该搜索算法要求被搜索的数据结构已排序。

选择数组的中间值
如果中间值是待搜索值，那么算法执行结束
如果待搜索的值比中间值小，则返回第一步，在选中值得左边寻找
如果待搜索的值比中间值大，则返回第二步，在选中值得右边寻找

代码实现：
    let binarySearch = function(item){
        // 因为要求先排序
        quickSort(array);
        
        let low = 0,
            hight = array.length - 1,
            mid,element;
        
        while (low <= high){
            mid = Math.floor((low + high) / 2);
            element = array[mid];
            if(element < item){
                low = mid + 1;
            }else if(element>item){
                high = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
一下是算法执行的步骤示例图：

这里的内容大部分是书中摘抄的内容，中间说到了快速排序，您可以查阅其它的资料去了解下，排序算法相关的内容，JS常见的排序算法主要有，当然我们这里也可以使用其它排序方法，比如：冒泡排序、选择排序、插入排序、归并排序等。

云服务器 GPU云服务器算法与数据结构数据结构与算法搜索算法数据结构与算法教程

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95739.html

学习JavaScript数据结构与算法 — 深度优先搜索算法

摘要：深度优先搜索上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。用深度优先搜索算法对图中的任务图进行拓扑排序最终各顶点的发现和探索完成时间会保存在中。深度优先搜索（DFS）上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中深度优先搜索算法会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶点，接着原路回退并探索下一条路径。换句话说，它是先深度后广...

李增田 2019-08-22 11:09 评论0 收藏0
学习JavaScript数据结构与算法 — 广度优先搜索算法

摘要：广度优先搜索上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。其它最短路径算法对于加权图的最短路径，广度优先算法可能并不合适。广度优先搜索（BFS）上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的...

eternalshallow 2019-08-22 11:09 评论0 收藏0
算法系列——JavaScript中广度优先搜索思想实现

摘要：散列表上面的地图向我们展示了如何用广度优先搜索的思想找到北京到广州的最短路线。在广度优先搜索中，我们需要用到队列的这种思想来实现查找。建立了下面这个模型武汉广州西藏上海上海武汉广州代码完整实现，利用递归和广度优先搜索的思想实现。什么是广度优先搜索？如果只是是背概念，幼儿园的小朋友都能背下来念给你听。假设看这篇文章的都和我一样是个前端工程师，我们要从广度优先搜索（BFS）中学到什么...

everfly 2019-08-21 17:36 评论0 收藏0