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

在本篇文章中，將為各位老鐵介紹不同的搜索算法以及它們的復(fù)雜度。因?yàn)榱η笸ㄋ滓锥云赡茌^長(zhǎng)，大伙可以先Mark下來(lái)，每天抽時(shí)間看一點(diǎn)理解一點(diǎn)。本文配套的Github Repo，歡迎各位老鐵star，會(huì)一直更新的。

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

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

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

    return false;
}

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

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ù)的中間開(kāi)始，檢查中間的項(xiàng)是否比我們要尋找的項(xiàng)小或大，并決定走哪條路。這樣，我們把列表分成兩半，一半完全丟棄，像下面的圖像一樣。

遞歸版本：

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

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

有這樣一個(gè)場(chǎng)景，假如我們有一個(gè)含有重復(fù)數(shù)據(jù)的數(shù)組，如果我們想從數(shù)組中找到2的第一次出現(xiàn)的位置，使用之前的算法將會(huì)返回第5個(gè)元素。然而，從下面的圖像中我們可以清楚地看到，正確的結(jié)果告訴我們它不是第5個(gè)元素，而是第2個(gè)元素。因此，上述二分搜索算法需要進(jìn)行修改，將它修改成一個(gè)重復(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所對(duì)應(yīng)的值是否是我們正在尋找的值。 如果是，那么我們將中間索引指定為第一次出現(xiàn)的index，我們繼續(xù)檢查中間元素左側(cè)的元素，看看有沒(méi)有再次出現(xiàn)我們尋找的值。 然后繼續(xù)迭代，直到$low > $high。 如果沒(méi)有再次找到這個(gè)值，那么第一次出現(xiàn)的位置就是該項(xiàng)的第一個(gè)索引的值。 如果沒(méi)有，像往常一樣返回-1。我們運(yùn)行一個(gè)測(cè)試來(lái)看代碼是否正確：

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)用二分搜索會(huì)導(dǎo)致錯(cuò)誤的結(jié)果。 那可能存在一種情況，就是對(duì)于某個(gè)數(shù)組，我們不確定它是否已排序?，F(xiàn)在有一個(gè)問(wèn)題就是，是否應(yīng)該首先對(duì)數(shù)組進(jìn)行排序然后應(yīng)用二分查找算法嗎？還是繼續(xù)使用線性搜索算法？

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

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

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

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

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

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

可以發(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;
    
}

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

在二分搜索中，我們?cè)谡麄€(gè)列表中搜索給定的數(shù)據(jù)。指數(shù)搜索通過(guò)決定搜索的下界和上界來(lái)改進(jìn)二分搜索，這樣我們就不會(huì)搜索整個(gè)列表。它減少了我們?cè)谒阉鬟^(guò)程中比較元素的數(shù)量。指數(shù)搜索是在以下兩個(gè)步驟中完成的：

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

下面我們來(lái)看下PHP實(shí)現(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èi)的時(shí)間復(fù)雜度就是O(logi)。表示為了找到上邊界，我們的while循環(huán)需要執(zhí)行O(logi)次。因?yàn)橄乱徊綉?yīng)用一個(gè)二分搜索，時(shí)間復(fù)雜度也是O(logi)。我們假設(shè)j是我們上一個(gè)while循環(huán)執(zhí)行的次數(shù)，那么本次二分搜索我們需要搜索的范圍就是2^j-1 至 2^j，而j=logi，即

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

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

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

PHP底層C實(shí)現(xiàn)中數(shù)組本身就是一個(gè)哈希表，由于數(shù)組是動(dòng)態(tài)的，不必?fù)?dān)心數(shù)組溢出。我們可以將值存儲(chǔ)在關(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)建搜索樹(shù)。在第理解和實(shí)現(xiàn)樹(shù)中，我們了解了如何構(gòu)建二叉搜索樹(shù)并提高搜索效率，并且介紹了遍歷樹(shù)的不同方法。 現(xiàn)在，繼續(xù)介紹兩種最常用的搜索樹(shù)的方法，通常稱為廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）。

在樹(shù)結(jié)構(gòu)中，根連接到其子節(jié)點(diǎn)，每個(gè)子節(jié)點(diǎn)還可以繼續(xù)表示為樹(shù)。 在廣度優(yōu)先搜索中，我們從節(jié)點(diǎn)（主要是根節(jié)點(diǎn)）開(kāi)始，并且在訪問(wèn)其他鄰居節(jié)點(diǎn)之前首先訪問(wèn)所有相鄰節(jié)點(diǎn)。 換句話說(shuō)，我們?cè)谑褂肂FS時(shí)必須逐級(jí)移動(dòng)。

使用BFS，會(huì)得到以下的序列。

偽代碼如下：

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

完整的例子和測(cè)試，你可以點(diǎn)擊這里查看。

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

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

深度優(yōu)先搜索（DFS）指的是從一個(gè)節(jié)點(diǎn)開(kāi)始搜索，并從目標(biāo)節(jié)點(diǎn)通過(guò)分支盡可能深地到達(dá)節(jié)點(diǎn)。 DFS與BFS不同，簡(jiǎn)單來(lái)說(shuō)，就是DFS是深入挖掘而不是先擴(kuò)散。DFS在到達(dá)分支末尾時(shí)然后向上回溯，并移動(dòng)到下一個(gè)可用的相鄰節(jié)點(diǎn)，直到搜索結(jié)束。還是上面的樹(shù)

這次我們會(huì)獲得不通的遍歷順序：

從根開(kāi)始，然后訪問(wèn)第一個(gè)孩子，即3。然后，到達(dá)3的子節(jié)點(diǎn)，并反復(fù)執(zhí)行此操作，直到我們到達(dá)分支的底部。在DFS中，我們將采用遞歸方法來(lái)實(shí)現(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;
}

如果需要使用迭代實(shí)現(xiàn)，必須記住使用棧而不是隊(duì)列來(lái)跟蹤要訪問(wèn)的下一個(gè)節(jié)點(diǎn)。下面使用迭代方法的實(shí)現(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;
}

這看起來(lái)與BFS算法非常相似。主要區(qū)別在于使用棧而不是隊(duì)列來(lái)存儲(chǔ)被訪問(wèn)節(jié)點(diǎn)。它會(huì)對(duì)結(jié)果產(chǎn)生影響。上面的代碼將輸出8 10 14 13 3 6 7 4 1。這與我們使用迭代的算法輸出不同，但其實(shí)這個(gè)結(jié)果沒(méi)有毛病。

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

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），通過(guò)反轉(zhuǎn)，可以確保先訪問(wèn)第一個(gè)節(jié)點(diǎn)，因?yàn)轭嵉沽隧樞?，棧?shí)際上就作為隊(duì)列在工作。要是我們搜索的是二叉樹(shù)，就不需要任何反轉(zhuǎn)，因?yàn)槲覀兛梢赃x擇先將右孩子入棧，然后左子節(jié)點(diǎn)首先出棧。

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