【原】PHP數(shù)據(jù)結(jié)構(gòu)-線性查找與二分查找

硬核項目經(jīng)理 2021-05-31

展開全文

線性查找與二分查找

歡迎來到查找的世界，在學(xué)習(xí)完各種數(shù)據(jù)結(jié)構(gòu)之后，總算走到了這一步，不知道大家有什么感想呢？反正我是邊學(xué)邊忘，現(xiàn)在讓我去說說圖的那幾個算法還是在蒙圈的狀態(tài)中。不過學(xué)習(xí)嘛，就是一步一步的來，暫時搞不懂的東西其實也是可以放一放的。打破砂鍋和堅持不懈當(dāng)然是好的品德，但有些東西可能真的是需要時間去消化的，甚至可能是需要真實的項目經(jīng)歷才能徹底搞明白。在我們編程行業(yè)來說就是典型的這種實踐的學(xué)習(xí)形式效果會更好，很多人在上大學(xué)的時候?qū)τ跀?shù)據(jù)結(jié)構(gòu)以及其它專業(yè)課都是以死記硬背為主，包括上了多少年班的同學(xué)可能都沒有在業(yè)務(wù)代碼中真正的使用過什么算法，所以理解它們確實是非常困難的。這時，我們可以暫時休息一下，轉(zhuǎn)換一下思路，學(xué)習(xí)最主要的就是預(yù)習(xí)和復(fù)習(xí)，在這次學(xué)習(xí)完之后，將來再進行多次的復(fù)習(xí)，研究各種不同的資料，遲早有一天大家都能搞明白的。

今天的內(nèi)容其實就非常簡單了，可以說是除了線性表之外最簡單的內(nèi)容。我們只研究兩個非常初級的查找，那就是順序查找和折半查找。相信不少同學(xué)可能早就會了，一般培訓(xùn)機構(gòu)講數(shù)據(jù)結(jié)構(gòu)和算法時，查找必講二分，排序必講冒泡，更不用說正規(guī)大學(xué)對口專業(yè)出身的同學(xué)了。當(dāng)然，這兩個也是非常簡單的，不管你有沒有基礎(chǔ)，咱們一起來看看吧。

不管你是什么算法題，還是在實際的業(yè)務(wù)開發(fā)中，查找都是非常重要的，甚至可能比排序還要重要。想想你整天面向數(shù)據(jù)庫編程是在干嘛？不就是 CRUD 嘛，其中大部的業(yè)務(wù)還都是以搜索查找居多，我們在優(yōu)化數(shù)據(jù)庫時，也主要是優(yōu)化各種查詢語句。當(dāng)然，要說到數(shù)據(jù)庫的查找那就太高深了，以后我們學(xué)習(xí) MySQL 相關(guān)的知識時再詳細講解，特別是索引中的 B+ 樹，就是數(shù)據(jù)結(jié)構(gòu)和算法的核心思想的體現(xiàn)。好吧，不吹牛了，也不敢在這里多說了，因為自己也沒研究透呢。

線性查找（順序查找）

顧名思義，不管是叫線性還是叫順序，很明顯，就是一條數(shù)據(jù)一條數(shù)據(jù)的對比下去就好啦。

function SearchSeq($sk, $arr)
{
    for ($i = 0; $i < count($arr); $i++) {
        if ($sk == $arr[$i]) {
            echo $i, PHP_EOL;
            break;
        }
    }
    echo "線性查找次數(shù)：" . $i, PHP_EOL;
}

嗯，真的是連解釋都不想解釋了，這段代碼要是看不懂的話就先去復(fù)習(xí)下基本的循環(huán)和條件判斷語句吧！很明顯，一次線性查找的時間復(fù)雜度就是 O(N) 。

二分查找（折半查找）

既然都這么簡單，那么我們再直接給出折半查找的代碼。

function SearchBin($sk, $arr){
    $left = 0;
    $right = count($arr) - 1;
    $i = 0;
    while ($left <= $right) {
        $i++;
        $mid = (int) (($left + $right) / 2);
        if ($arr[$mid] > $sk) {
            $right = $mid - 1;
        } else if ($arr[$mid] < $sk) {
            $left = $mid + 1;
        } else {
            echo $mid, PHP_EOL;
            break;
        }
    }
    echo "折半查找次數(shù)：" . $i, PHP_EOL;
}

折半查找的前提是數(shù)據(jù)必須是有序的，這樣我們就可以根據(jù)數(shù)據(jù)問題的長度來獲取中間的數(shù)，然后跟要對比的數(shù)進行比較，如果小于這個數(shù)，就在前一半數(shù)據(jù)中查找，如果大于這個數(shù)，就在后一半部分中進行查找。一會看例子再詳細說明。

對比

兩個算法其實都很簡單，我們直接看看他們的運行情況和效率區(qū)別。

$arr = [5, 6, 19, 25, 4, 33, 56, 77, 82, 81, 64, 37, 91, 23];

// 輸入 56
fscanf(STDIN, "%d", $searchKey);

SearchSeq($searchKey, $arr);
// 6
// 線性查找次數(shù)：6

sort($arr);
print_r($arr);

SearchBin($searchKey, $arr);
// 8
// 折半查找次數(shù)：3

首先我們定義了一個數(shù)組，其實就是隨便給了一些數(shù)據(jù)。然后輸入一個數(shù)據(jù)，查找它在數(shù)組中的位置。比如我們在測試代碼中輸入了 56 ，線性查找是循環(huán)進行了 6 次，找到 56 所在的位置為下標(biāo) 6 的位置。

對于折半查找來說，我們需要先給數(shù)組排序，這時 56 會排在下標(biāo)為 8 的位置，而在折半查找的循環(huán)中，我們只循環(huán)了 3 次就找到了這個位置。是不是感覺快了很多，一下就快了一倍。這可不是它的真正實力哦，折半查找的真實實力是對數(shù) 級別的效率，也就是它的時間復(fù)雜度為 O(logN) 。我們先來結(jié)合上面的代碼看下它這三次循環(huán)都干了什么。

第一次進入，mid 為 6 (0+13=13，除2)，下標(biāo)為 arr[6] 的值為 3 ，比 56 小，所以 left = 6+1 = 7
第二輪循環(huán)，mid 為 10（7+13=20，除2），下標(biāo)為 arr[10] 的值為 77 ，比 56 大，所以 right = 10-1 = 9
第三輪循環(huán)，mid 為 9（7+9=16，除2），下標(biāo)為 arr[8] 的值為 56，結(jié)束

其實很多猜數(shù)字的游戲也都是這么玩的，比如給你一個范圍，0-100的數(shù)，猜他寫下的是哪個數(shù)，最快最簡單的方法也就是這種折半查找的方式，我們只需要最多 7 次就可以猜出 100 以內(nèi)的數(shù)。很明顯，這就是對數(shù)的威力。下面我們再來看一個更直觀的，十萬個有序的數(shù)，我們就找最后那一個數(shù)，看看順序查找和折半查找能有多大差距。

$arr = range(1, 100000);
$searchKey = 100000;

SearchSeq($searchKey, $arr);
// 99999
// 線性查找次數(shù)：99999

SearchBin($searchKey, $arr);
// 99999
// 折半查找次數(shù)：17

嗨不嗨，這就是對數(shù)的威力?。∥覀冃枰?2 的 7 次方才能覆蓋 100 以內(nèi)的數(shù)，但我們只需要 2 的 17 次方，就能覆蓋十萬以內(nèi)的數(shù)，這個效率差距還是隨著 N 的越來越大而越來越明顯的。

總結(jié)

今天的內(nèi)容是不是很簡單，雖說內(nèi)容簡單，但是我們卻見識到了不同算法效率之間的巨大差異。當(dāng)然，折半查找也有其本身的局限，那就是數(shù)據(jù)必須是的序的，當(dāng)然，在合適的情況下我們也可以選用一個 O(logN) 的排序算法，這樣總體的時間復(fù)雜度就還能保持在對數(shù)級別了?？傊?，先掌握好這些簡單的內(nèi)容，千萬別在面試的時候連這一關(guān)都過不了哦！

測試代碼：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/6.查找/source/6.1線性查找與二分查找.php

參考文檔：

《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴蔚敏

《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越

《數(shù)據(jù)結(jié)構(gòu)高分筆記》2020版，天勤考研