javascript數據結構與算法——搜索算法

TZLLOG 發布于2019-08-22 18:19 / 1155人閱讀

摘要：前言本書當中說了兩種搜索算法，篇幅都不大，因為融合了之前的知識點，所以看起來會相對簡單一，主要包括兩個內容順序搜索二分搜索順序搜索從字面的意思來看，就是按照順序一個一個找下去的意思，直到找到為止。該搜索算法要求被搜索的數據結構已排序。

前言

本書當中說了兩種搜索算法，篇幅都不大，因為融合了之前的知識點，所以看起來會相對簡單一，主要包括兩個內容：

順序搜索

二分搜索

順序搜索

??從字面的意思來看，就是按照順序一個一個找下去的意思，直到找到為止。搜索的結果可以返回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云服務器算法與數據結構數據結構與算法搜索算法數據結構與算法教程

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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