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

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

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

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

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

    return false;
}

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

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;
}

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

遞歸版本：

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;
    }
}

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

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

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所對應(yīng)的值是否是我們正在尋找的值。 如果是，那么我們將中間索引指定為第一次出現(xiàn)的index，我們繼續(xù)檢查中間元素左側(cè)的元素，看看有沒有再次出現(xiàn)我們尋找的值。 然后繼續(xù)迭代，直到$low > $high。 如果沒有再次找到這個值，那么第一次出現(xiàn)的位置就是該項的第一個索引的值。 如果沒有，像往常一樣返回-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);
}

發(fā)現(xiàn)結(jié)果正確。

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

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

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

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

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

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

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

可以發(fā)現(xiàn)，我們將從通用的mid =（low * high)/2 轉(zhuǎn)變?yōu)楦鼜?fù)雜的等式。如果搜索的值更接近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;
    
}

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

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

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

下面我們來看下PHP實現(xiàn)的代碼

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出現(xiàn)的位置記位i，那么我們第一步花費的時間復(fù)雜度就是O(logi)。表示為了找到上邊界，我們的while循環(huán)需要執(zhí)行O(logi)次。因為下一步應(yīng)用一個二分搜索，時間復(fù)雜度也是O(logi)。我們假設(shè)j是我們上一個while循環(huán)執(zhí)行的次數(shù)，那么本次二分搜索我們需要搜索的范圍就是2^j-1 至 2^j，而j=logi，即

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

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

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

PHP底層C實現(xiàn)中數(shù)組本身就是一個哈希表，由于數(shù)組是動態(tài)的，不必擔心數(shù)組溢出。我們可以將值存儲在關(guān)聯(lián)數(shù)組中，以便我們可以將值與鍵相關(guān)聯(lián)。

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

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

在樹結(jié)構(gòu)中，根連接到其子節(jié)點，每個子節(jié)點還可以繼續(xù)表示為樹。 在廣度優(yōu)先搜索中，我們從節(jié)點（主要是根節(jié)點）開始，并且在訪問其他鄰居節(jié)點之前首先訪問所有相鄰節(jié)點。 換句話說，我們在使用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;
    }
}

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

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

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

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

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

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

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;
}

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

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算法非常相似。主要區(qū)別在于使用棧而不是隊列來存儲被訪問節(jié)點。它會對結(jié)果產(chǎn)生影響。上面的代碼將輸出8 10 14 13 3 6 7 4 1。這與我們使用迭代的算法輸出不同，但其實這個結(jié)果沒有毛病。

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

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，F(xiàn)irst-out（LIFO），通過反轉(zhuǎn)，可以確保先訪問第一個節(jié)點，因為顛倒了順序，棧實際上就作為隊列在工作。要是我們搜索的是二叉樹，就不需要任何反轉(zhuǎn)，因為我們可以選擇先將右孩子入棧，然后左子節(jié)點首先出棧。

DFS的時間復(fù)雜度類似于BFS。