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

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

展開(kāi)全文

線性查找與二分查找

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

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

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

線性查找（順序查找）

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

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)和條件判斷語(yǔ)句吧！很明顯，一次線性查找的時(shí)間復(fù)雜度就是 O(N) 。

二分查找（折半查找）

既然都這么簡(jiǎn)單，那么我們?cè)僦苯咏o出折半查找的代碼。

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ù)問(wèn)題的長(zhǎng)度來(lái)獲取中間的數(shù)，然后跟要對(duì)比的數(shù)進(jìn)行比較，如果小于這個(gè)數(shù)，就在前一半數(shù)據(jù)中查找，如果大于這個(gè)數(shù)，就在后一半部分中進(jìn)行查找。一會(huì)看例子再詳細(xì)說(shuō)明。

對(duì)比

兩個(gè)算法其實(shí)都很簡(jiǎn)單，我們直接看看他們的運(yùn)行情況和效率區(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

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

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

第一次進(jì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í)很多猜數(shù)字的游戲也都是這么玩的，比如給你一個(gè)范圍，0-100的數(shù)，猜他寫下的是哪個(gè)數(shù)，最快最簡(jiǎn)單的方法也就是這種折半查找的方式，我們只需要最多 7 次就可以猜出 100 以內(nèi)的數(shù)。很明顯，這就是對(duì)數(shù)的威力。下面我們?cè)賮?lái)看一個(gè)更直觀的，十萬(wàn)個(gè)有序的數(shù)，我們就找最后那一個(gè)數(shù)，看看順序查找和折半查找能有多大差距。

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

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

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

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

總結(jié)

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

測(cè)試代碼：

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

參考文檔：

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

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

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