摘要：我們現在來看二分搜索算法的兩種變形插值搜索和指數搜索。插值搜索是對二分搜索算法的改進，插值搜索可以基于搜索的值選擇到達不同的位置。

在本篇文章中，將為各位老鐵介紹不同的搜索算法以及它們的復雜度。因為力求通俗易懂，所以篇幅可能較長，大伙可以先Mark下來，每天抽時間看一點理解一點。本文配套的Github Repo，歡迎各位老鐵star，會一直更新的。

和排序類似，搜索或者叫做查找，也是平時我們使用最多的算法之一。無論我們搜索數據庫還是文件，實際上都在使用某種搜索算法來定位想要查找的數據。

執行搜索的最常見的方法是將每個項目與我們正在尋找的數據進行比較，這就是線性搜索或順序搜索。它是執行搜索的最基本的方式。如果列表中有n項。在最壞的情況下。我們必須搜索n個項目才能找到一個特定的項目。下面遍歷一個數組來查找一個項目。

function linearSearch(array $arr, int $needle) {
    for ($i = 0, $count = count($arr); $i < $count; $i++) {
        if ($needle === $arr[$i]) {
            return true;
        }
    }

    return false;
}

線性搜索的平均時間復雜度或最壞時間復雜度是O(n)，這不會隨著待搜索數組的順序改變而改變。所以如果數組中的項按特定順序排序，我們不必進行線性搜索。我們可以通過執行選擇性搜索而可以獲得更好的結果。最流行也是最著名的搜索算法是“二分搜索”。雖然有點像我們之前說的二叉搜索樹，但我們不用構造二叉搜索樹就可以使用這個算法。

function binarySearch(array $arr, int $needle) {
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        $middle = (int)(($high + $low) / 2);

        if ($arr[$middle] < $needle) {
            $low = $middle + 1;
        } elseif ($arr[$middle] > $needle) {
            $high = $middle - 1;
        } else {
            return true;
        }
    }

    return false;
}

在二分搜索算法中，我們從數據的中間開始，檢查中間的項是否比我們要尋找的項小或大，并決定走哪條路。這樣，我們把列表分成兩半，一半完全丟棄，像下面的圖像一樣。

遞歸版本：

function binarySearchRecursion(array $arr, int $needle, int $low, int $high)
{
    if ($high < $low) return false;

    $middle = (int)(($high + $low) / 2);

    if ($arr[$middle] < $needle) {
        return binarySearchRecursion($arr, $needle, $middle + 1, $high);
    } elseif ($arr[$middle] > $needle) {
        return binarySearchRecursion($arr, $needle, $low, $middle - 1);
    } else {
        return true;
    }
}

對于每一次迭代，我們將數據劃分為兩半，丟棄一半，另一半用于搜索。在分別進行了1，2次和3次迭代之后，我們的列表長度逐漸減少到n/2，n/4，n/8...。因此，我們可以發現，k次迭代后，將只會留下n/2^k項。最后的結果就是 n/2^k = 1，然后我們兩邊分別取對數 得到 k = log(n)，這就是二分搜索算法的最壞運行時間復雜度。

有這樣一個場景，假如我們有一個含有重復數據的數組，如果我們想從數組中找到2的第一次出現的位置，使用之前的算法將會返回第5個元素。然而，從下面的圖像中我們可以清楚地看到，正確的結果告訴我們它不是第5個元素，而是第2個元素。因此，上述二分搜索算法需要進行修改，將它修改成一個重復的搜索，搜索直到元素第一次出現的位置才停止。

function repetitiveBinarySearch(array $data, int $needle)
{
    $low = 0;
    $high = count($data);
    $firstIndex = -1;

    while ($low <= $high) {
        $middle = ($low + $high) >> 1;

        if ($data[$middle] === $needle) {
            $firstIndex = $middle;
            $high = $middle - 1;
        } elseif ($data[$middle] > $needle) {
            $high = $middle - 1;
        } else {
            $low = $middle + 1;
        }
    }

    return $firstIndex;
}

首先我們檢查mid所對應的值是否是我們正在尋找的值。 如果是，那么我們將中間索引指定為第一次出現的index，我們繼續檢查中間元素左側的元素，看看有沒有再次出現我們尋找的值。 然后繼續迭代，直到$low > $high。 如果沒有再次找到這個值，那么第一次出現的位置就是該項的第一個索引的值。 如果沒有，像往常一樣返回-1。我們運行一個測試來看代碼是否正確：

public function testRepetitiveBinarySearch()
{
    $arr = [1,1,1,2,3,4,5,5,5,5,5,6,7,8,9,10];

    $firstIndex = repetitiveBinarySearch($arr, 6);

    $this->assertEquals(11, $firstIndex);
}

發現結果正確。

到目前為止，我們可以得出結論，二分搜索肯定比線性搜索更快。但是，這一切的先決條件是數組已經排序。在未排序的數組中應用二分搜索會導致錯誤的結果。 那可能存在一種情況，就是對于某個數組，我們不確定它是否已排序。現在有一個問題就是，是否應該首先對數組進行排序然后應用二分查找算法嗎？還是繼續使用線性搜索算法？

對于一個包含n個項目的數組，并且它們沒有排序。由于我們知道二分搜索更快，我們決定先對其進行排序，然后使用二分搜索。但是，我們清楚最好的排序算法，其最差的時間復雜度是O(nlogn)，而對于二分搜索，最壞情況復雜度是O（logn)。所以，如果我們排序后應用二分搜索，復雜度將是O（nlogn）。

但是，我們也知道，對于任何線性或順序搜索（排序或未排序），最差的時間復雜度是O（n），顯然好于上述方案。

考慮另一種情況，即我們需要多次搜索給定數組。我們將k表示為我們想要搜索數組的次數。如果k為1，那么我們可以很容易地應用之前的線性搜索方法。如果k的值比數組的大小更小，暫且使用n表示數組的大小。如果k的值更接近或大于n，那么我們在應用線性方法時會遇到一些問題。假設k = n，線性搜索將具有O（n2）的復雜度。現在，如果我們進行排序然后再進行搜索，那么即使k更大，一次排序也只會花費O（nlogn）時間復。然后，每次搜索的復雜度是O（logn），n次搜索的復雜度是O（nlogn）。如果我們在這里采取最壞的運行情況，排序后然后搜索k次總的的復雜度是O（nlogn），顯然這比順序搜索更好。

我們可以得出結論，如果一些搜索操作的次數比數組的長度小，最好不要對數組進行排序，直接執行順序搜索即可。但是，如果搜索操作的次數與數組的大小相比更大，那么最好先對數組進行排序，然后使用二分搜索。

二分搜索算法有很多不同的版本。我們不是每次都選擇中間索引，我們可以通過計算作出決策來選擇接下來要使用的索引。我們現在來看二分搜索算法的兩種變形：插值搜索和指數搜索。

在二分搜索算法中，總是從數組的中間開始搜索過程。 如果一個數組是均勻分布的，并且我們正在尋找的數據可能接近數組的末尾，那么從中間搜索可能不是一個好選擇。 在這種情況下，插值搜索可能非常有用。插值搜索是對二分搜索算法的改進，插值搜索可以基于搜索的值選擇到達不同的位置。例如，如果我們正在搜索靠近數組開頭的值，它將直接定位到到數組的第一部分而不是中間。使用公式計算位置，如下所示

可以發現，我們將從通用的mid =（low * high)/2 轉變為更復雜的等式。如果搜索的值更接近arr[high]，則此公式將返回更高的索引，如果值更接近arr[low]，則此公式將返回更低的索引。

function interpolationSearch(array $arr, int $needle)
{
    $low = 0;
    $high = count($arr) - 1;

    while ($arr[$low] != $arr[$high] && $needle >= $arr[$low] && $needle <= $arr[$high]) {
        $middle = intval($low + ($needle - $arr[$low]) * ($high - $low) / ($arr[$high] - $arr[$low]));

        if ($arr[$middle] < $needle) {
            $low = $middle + 1;
        } elseif ($arr[$middle] > $needle) {
            $high = $middle - 1;
        } else {
            return $middle;
        }
    }

    if ($needle == $arr[$low]) {
        return $low;
    } 
    
    return -1;
    
}

插值搜索需要更多的計算步驟，但是如果數據是均勻分布的，這個算法的平均復雜度是O(log(log n))，這比二分搜索的復雜度O(logn)要好得多。 此外，如果值的分布不均勻，我們必須要小心。 在這種情況下，插值搜索的性能可以需要重新評估。下面我們將探索另一種稱為指數搜索的二分搜索變體。

在二分搜索中，我們在整個列表中搜索給定的數據。指數搜索通過決定搜索的下界和上界來改進二分搜索，這樣我們就不會搜索整個列表。它減少了我們在搜索過程中比較元素的數量。指數搜索是在以下兩個步驟中完成的：

1.我們通過查找第一個指數k來確定邊界大小，其中值2^k的值大于搜索項。 現在，2^k和2^(k-1)分別成為上限和下限。
2.使用以上的邊界來進行二分搜索。

下面我們來看下PHP實現的代碼

function exponentialSearch(array $arr, int $needle): int
{
    $length = count($arr);
    if ($length == 0) return -1;

    $bound = 1;

    while ($bound < $length && $arr[$bound] < $needle) {
        $bound *= 2;
    }

    return binarySearchRecursion($arr, $needle, $bound >> 1, min($bound, $length));
}

我們把$needle出現的位置記位i，那么我們第一步花費的時間復雜度就是O(logi)。表示為了找到上邊界，我們的while循環需要執行O(logi)次。因為下一步應用一個二分搜索，時間復雜度也是O(logi)。我們假設j是我們上一個while循環執行的次數，那么本次二分搜索我們需要搜索的范圍就是2^j-1 至 2^j，而j=logi，即

那我們的二分搜索時間復雜度需要對這個范圍求log2，即

那么整個指數搜索的時間復雜度就是2 O(logi)，省略掉常數就是O(logi)。

在搜索操作方面，哈希表可以是非常有效的數據結構。在哈希表中，每個數據都有一個與之關聯的唯一索引。如果我們知道要查看哪個索引，我們就可以非常輕松地找到對應的值。通常，在其他編程語言中，我們必須使用多帶帶的哈希函數來計算存儲值的哈希索引。散列函數旨在為同一個值生成相同的索引，并避免沖突。

PHP底層C實現中數組本身就是一個哈希表，由于數組是動態的，不必擔心數組溢出。我們可以將值存儲在關聯數組中，以便我們可以將值與鍵相關聯。

function hashSearch(array $arr, int $needle)
{
    return isset($arr[$needle]) ? true : false;
}

搜索分層數據的最佳方案之一是創建搜索樹。在第理解和實現樹中，我們了解了如何構建二叉搜索樹并提高搜索效率，并且介紹了遍歷樹的不同方法。 現在，繼續介紹兩種最常用的搜索樹的方法，通常稱為廣度優先搜索（BFS）和深度優先搜索（DFS）。

在樹結構中，根連接到其子節點，每個子節點還可以繼續表示為樹。 在廣度優先搜索中，我們從節點（主要是根節點）開始，并且在訪問其他鄰居節點之前首先訪問所有相鄰節點。 換句話說，我們在使用BFS時必須逐級移動。

使用BFS，會得到以下的序列。

偽代碼如下：

procedure BFS(Node root)
    Q := empty queue
    Q.enqueue(root)
    
    while(Q != empty) 
        u := Q.dequeue()
        for each node w that is childnode of u
            Q.enqueue(w)
        end for each
    end while
end procedure        

下面是PHP代碼。

class TreeNode
{
    public $data = null;
    public $children = [];

    public function __construct(string $data = null)
    {
        $this->data = $data;
    }

    public function addChildren(TreeNode $treeNode)
    {
        $this->children[] = $treeNode;
    }
}

class Tree
{
    public $root = null;

    public function __construct(TreeNode $treeNode)
    {
        $this->root = $treeNode;
    }

    public function BFS(TreeNode $node): SplQueue
    {
        $queue = new SplQueue();
        $visited = new SplQueue();

        $queue->enqueue($node);

        while (!$queue->isEmpty()) {
            $current = $queue->dequeue();
            $visited->enqueue($current);

            foreach ($current->children as $children) {
                $queue->enqueue($children);
            }
        }

        return $visited;
    }
}

完整的例子和測試，你可以點擊這里查看。

如果想要查找節點是否存在，可以為當前節點值添加簡單的條件判斷即可。BFS最差的時間復雜度是O（|V| + |E|），其中V是頂點或節點的數量，E則是邊或者節點之間的連接數，最壞的情況空間復雜度是O（|V|）。

圖的BFS和上面的類似，但略有不同。 由于圖是可以循環的（可以創建循環），需要確保我們不會重復訪問同一節點以創建無限循環。 為了避免重新訪問圖節點，必須跟蹤已經訪問過的節點。可以使用隊列，也可以使用圖著色算法來解決。

深度優先搜索（DFS）指的是從一個節點開始搜索，并從目標節點通過分支盡可能深地到達節點。 DFS與BFS不同，簡單來說，就是DFS是深入挖掘而不是先擴散。DFS在到達分支末尾時然后向上回溯，并移動到下一個可用的相鄰節點，直到搜索結束。還是上面的樹

這次我們會獲得不通的遍歷順序：

從根開始，然后訪問第一個孩子，即3。然后，到達3的子節點，并反復執行此操作，直到我們到達分支的底部。在DFS中，我們將采用遞歸方法來實現。

procedure DFS(Node current)
    for each node v that is childnode of current
       DFS(v)
    end for each
end procedure

 public function DFS(TreeNode $node): SplQueue
{
    $this->visited->enqueue($node);

    if ($node->children) {
        foreach ($node->children as $child) {
            $this->DFS($child);
        }
    }

    return $this->visited;
}

如果需要使用迭代實現，必須記住使用棧而不是隊列來跟蹤要訪問的下一個節點。下面使用迭代方法的實現

public function DFS(TreeNode $node): SplQueue
{
    $stack = new SplStack();
    $visited = new SplQueue();

    $stack->push($node);

    while (!$stack->isEmpty()) {
        $current = $stack->pop();
        $visited->enqueue($current);

        foreach ($current->children as $child) {
            $stack->push($child);
        }
    }

    return $visited;
}

這看起來與BFS算法非常相似。主要區別在于使用棧而不是隊列來存儲被訪問節點。它會對結果產生影響。上面的代碼將輸出8 10 14 13 3 6 7 4 1。這與我們使用迭代的算法輸出不同，但其實這個結果沒有毛病。

因為使用棧來存儲特定節點的子節點。對于值為8的根節點，第一個值是3的子節點首先入棧，然后，10入棧。由于10后來入棧，它遵循LIFO。所以，如果我們使用棧實現DFS，則輸出總是從最后一個分支開始到第一個分支。可以在DFS代碼中進行一些小調整來達到想要的效果。

public function DFS(TreeNode $node): SplQueue
{
    $stack = new SplStack();
    $visited = new SplQueue();

    $stack->push($node);

    while (!$stack->isEmpty()) {
        $current = $stack->pop();
        $visited->enqueue($current);

        $current->children = array_reverse($current->children);
        foreach ($current->children as $child) {
            $stack->push($child);
        }
    }

    return $visited;
}

由于棧遵循Last-in，First-out（LIFO），通過反轉，可以確保先訪問第一個節點，因為顛倒了順序，棧實際上就作為隊列在工作。要是我們搜索的是二叉樹，就不需要任何反轉，因為我們可以選擇先將右孩子入棧，然后左子節點首先出棧。

DFS的時間復雜度類似于BFS。