導讀

大家好，很高興又和大家見面啦！！！

在前面的學習中，我們系統學習了兩種基礎而重要的查找算法：

• ??順序查找??作為最直觀的查找方式，盡管實現簡便但對數據無任何要求，其O(n)的時間復雜度在數據量大時效率較低。??
• 折半查找??則利用"二分法"思想將查找效率提升至O(log?n)，但要求數據必須有序且通常需要順序存儲。

在實際應用中，我們常常面臨這樣的困境：內容動態變化導致難以維持有序性，但又希望獲得較高的查找效率。正是為了解決這一矛盾，??分塊查找??應運而生！

本篇博客將深入探討分塊查找算法，它巧妙地將順序查找和折半查找的優點相結合：

• ??繼承順序查找的優點??：對數據有序性要求低，塊內元素可無序排列
• ??吸收折半查找的優點??：通過索引表的有序性實現快速定位
• ??創新性地引入分塊思想??：通過"塊內無序、塊間有序"的設計平衡了動態性與效率

文章將從分塊查找的基本思想入手，詳細講解兩種分塊方式（邏輯分配與物理分配）的建立細節，通過具體實例演示查找過程，并深入分析算法的平均查找長度。無論你是正在學習數據結構的學生，還是希望優化實際項目中查找效率的開發者，這篇文章都將為你提供寶貴的 insights。

讓大家一起探索這種兼具靈活性與效率的查找算法吧！

一、根本思想

分塊查找也稱索引順序查找，它吸取了順序查找和折半查找各自的優點，即有動態結構，有適合快速查找。

其基本思想為：

• 將查找表分為若干個子塊
• 各自塊內部元素行無序，但是子塊與子塊之間必須有序
• 建立一個索引表，索引表中的每個元素包含各塊的最大關鍵字與各塊中的第一個元素地址
• 索引表按關鍵字有序排列

下面我們還是通過實例來理解其基本思想：

1.1 分塊過程

例如在關鍵碼集合：{88, 24, 72, 61, 21, 6, 32, 11, 8, 31, 22, 83, 78, 54} 中，我們按照某種規則對該集合進行分塊，如以跨度 $30$為單位進行分塊，我們就可以將該集合分為三塊：

• 第一塊：$(0,29)$
• 第二塊：$(30,59)$
• 第三塊：$(60,89)$

接下來我們可以根據該分塊從小到大的順序創建一個索引表

之后，我們只需要將各元素依次分配到各個分塊中即可，這里有兩種方式：

• 邏輯分配：我們通過在各分塊中記錄各元素的數組下標，完成邏輯上的分配
• 物理分配：我們利用對原數組進行物理重排，將各元素分配到各自的分塊中

兩種方式各自的優缺點分別為：

• 邏輯分塊：
  • 優點??：
    • 原數組保持完全不變，僅需額外存儲索引信息。
    • 適合動態數據（插入/刪除時只需更新索引表）。
  • 缺點??：
    • 需要額外空間存儲索引（如塊指針、范圍等）。
• 物理分塊：
  • 優點??：
    • 無需額外索引結構，內存效率高。
  • 缺點??：
    • 原數組順序被破壞??，可能影響其他依賴原始順序的操作。
    • 插入/刪除元素需重新分塊，效率較低。

下面我們分別來說明一下這兩種分配方式的具體過程：

1.1.1 邏輯分配

在邏輯分配中，我們需要完成兩件事：

• 找到各分塊中的元素最大值
• 記錄各分塊中的各元素下標

對于數組：{88, 24, 72, 61, 21, 6, 32, 11, 8, 31, 22, 83, 78, 54} 各元素下標分別為：

接下來，我們可以通過對數組進行遍歷，并將各元素及其下標記錄到各分塊中：

按照上圖的分配，對應的索引表需要更改為：最大值 + 元素下標的形式

現在我們就可以在不改變原有數組的情況下，通過索引表來查找各個元素了；

1.1.2 物理分配

在物理分配中，我們必須完成三件事：

• 找到各分塊中的元素最大值
• 將各分塊中的各元素動態分配到其對應分塊中
• 記錄各分塊首元素的地址

與邏輯分配相同的是，我們同樣需要憑借數組遍歷來查找各分塊的元素，查找的結果前面有介紹，這里我就不再贅述。

接下來我們就來看一下完成物理分配后得到的新數組：

按照上圖的分配，對應的索引表需要更改為：最大值 + 分塊起始元素下標的形式：

物理分配，每一個分塊內的元素均為無序：就是能夠看到，不管是邏輯分配，還

• 邏輯分配中，各分塊中的元素下標所對應的元素之間無序排列
• 物理分配中，各分塊中的元素之間無序排列

但是分塊之間有序：

• 邏輯分配中，其分塊索引表中的分塊索引按升序排列
• 物理分配中，其分塊索引表中的分塊索引按升序排列

二、查找過程

在分塊查找中，分為兩部分：

• 查找分塊索引表
  • 由于索引表是有序排列，因此，其查找過程既可以采用順序查找也可以采用折半查找；
• 查找索引值對應分塊
  • 由于分塊內的元素無序排列，因此，其查找過程只能采用順序查找

下面我們以物理分配為例來說明查找過程：

上圖所示數組對應的分塊索引表為：

下面大家分別以順序查找和折半查找為例，來說明查找元素33與21的整個過程；

2.1 索引表順序查找

在索引表中，我們按照從左到右的順序完成順序查找：

• 查找元素33：
  • 第一次關鍵字比較：$33>24$，元素不在該分區內
  • 第二次關鍵字比較：$33<54$，元素位于該分區內
• 查找元素21：
  • 第一次關鍵字比較：$21<24$，元素位于該分區內

2.2 索引表折半查找

在索引表中，我們通過指針 low 指向索引表最左側下標，即 low = 0，指針 high 指向索引表最右側下標，即 high = 2，之后完成折半查找：

• 查找元素33
  • 指針 mid = (high - low) / 2 + low = (2 - 0) / 2 + 0 = 1
  • 第一次關鍵字比較：$54>33$ 說明目標值位于小值區，我們需要更改指針 high 的右邊界指向
  • 更改指針 high：high = mid - 1 = 1 - 1 = 0
  • 指針 mid = (higih - low) / 2 + low = (0 - 0) / 2 + 0 = 0
  • 第二次關鍵字比較：$24<33$ 說明目標值位于大值區，我們需要更改指針 low 的左邊界指向
  • 更改指針low：low = mid + 1 = 0 + 1 = 1
  • 由于 low > high，說明此時元素 $33$位于分區2 中
• 查找元素21
  • 指針 mid = (high - low) / 2 + low = (2 - 0) / 2 + 0 = 1
  • 第一次關鍵字比較：$54>21$ 說明目標值位于小值區，我們需要更改指針 high 的右邊界指向
  • 更改指針 high：high = mid - 1 = 1 - 1 = 0
  • 指針 mid = (higih - low) / 2 + low = (0 - 0) / 2 + 0 = 0
  • 第二次關鍵字比較：$24>21$ 說明目標值位于小值區，我們需要更改指針 high 的右邊界指向
  • 更改指針high：high = mid - 1 = 0 - 1 = -1
  • 由于 low > high，說明此時元素 $21$位于分區1 中

在確定了分區后，接下來大家需要對確定好的分區進行順序查找！！！

2.3 分塊順序查找

從索引表中大家可以確定元素$33$位于分區2中：

通過順序查找，經過 3 次關鍵字比較后，我們并不能在分區中找到該元素，這說明原數組中并不存在該元素，因此本次查找失敗；

從索引表中我們許可確定元素$21$位于分區1中：

憑借順序查找，經過 2 次關鍵字比較，我們便找到了該元素，這時需要返回該元素的存儲位置；

三、平均查找長度

在分塊查找中，其平均查找長度由索引表和分區共同組成，即：

$$ASL=L_l+L_s$$

其中：$L_l$表示索引表內的查找長度，$L_s$為分區塊內的查找長度

若有一個長度為$n$的查找表，大家將其均勻地分為$b$塊，每塊中有$s$個記錄，在等概率情況下，其平均查找長度為：

• 索引表與塊內均采用順序查找：

$$\begin{array}{rl}AS{L}_{成功}& =L_l+L_s\\ & =\frac{b+1}{2}+\frac{s+1}{2}\\ & =\frac{b+s+2}{2}\\ & =\frac{\frac{n}{s}+s+2}{2}\\ & =\frac{s^2+2?s+n}{2?s}\\ AS{L}_{失敗1}& =L_l+L_s\\ & =\frac{b+1}{2}+s\\ & =\frac{\frac{n}{s}+1}{2}+s\\ & =\frac{2?s^2+s+n}{2?s}\\ AS{L}_{失敗2}& =L_l\\ & =\frac{b+1}{2}\\ & =\frac{\frac{n}{s}+1}{2}\\ & =\frac{n+s}{2?s}\end{array}$$

注：這里計算的失敗1指的是索引表查找成功，分塊查找失敗；失敗2指的是索引表查找失敗

• 索引表采用折半查找，塊內采用順序查找，假設索引表對應的判定樹為一棵滿二叉樹：

$$\begin{array}{rl}AS{L}_{成功}& =L_l+L_s\\ & =\sum _{i=1}^b{P}_i{C}_i+\sum _{j=1}^s{P}_j{C}_j\\ & =1?1?\frac{1}{b}+2?2?\frac{1}{b}+?+2^{h?1}?h?\frac{1}{b}+\frac{s+1}{2}\\ & =\frac{1?1+2?2+?+2^{h?1}?h}{b}+\frac{s+1}{2}\\ & =\frac{(h?1)?2^h+1}{b}+\frac{s+1}{2}\\ & =\frac{({\log }_2(b+1)?1)?2^{{\log }_2(b+1)}+1}{b}+\frac{s+1}{2}\\ & =\frac{(b+1)?{\log }_2(b+1)?b?1+1}{b}+\frac{s+1}{2}\\ & =\frac{(\frac{n}{s}+1)?{\log }_2(\frac{n}{s}+1)?\frac{n}{s}}{\frac{n}{s}}+\frac{s+1}{2}\\ & =\frac{\frac{(n+s)?{\log }_2(\frac{n+s}{s})?n}{s}}{\frac{n}{s}}+\frac{s+1}{2}\\ & =\frac{(n+s)?{\log }_2(\frac{n+s}{s})?n}{n}+\frac{s+1}{2}\\ AS{L}_{失敗}& =L_l+L_s\\ & =\sum _{i=1}^{b+1}{P}_i{C}_i+s\\ & =\frac{1}{b+1}?(h+1)+\frac{1}{b+1}?(h+1)+?+\frac{1}{b+1}?(h+1)+s\\ & =h+1+s\\ & ={\log }_2(b+1)+1+s\\ & ={\log }_2(\frac{n}{s}+1)+1+s\end{array}$$

現在我們以順序查找成功為例，其平均比較長度為：

$$AS{L}_{成功}=\frac{s^2+2?s+n}{2?s}$$

通過對該函數求導可得，當$s=\sqrt{n}$時，其平均查找長度取最小值：$\sqrt{n}+1$

在分塊查找中，雖然索引表占用了額外的存儲空間，索引查找也增加了一定的系統開銷，但由于其分塊結構，使得在塊內查找時的范圍較小，與順序查找相比，分塊查找的總體效率提升了不少。

從上述的平均查找長度分析來看，分塊查找的整體平均查找長度分析還是比較復雜的。

這重要體現在當我們對索引表采用折半查找時，它并不能像我們直接對有序查找表使用折半查找一樣，能夠直接確定查找表中是否存在該元素。

我們只能夠通過索引表確定查找值的所在分區，而具體的查找結果還需要通過對分塊內的元素進行更進一步的順序查找。

結語

通過本文的學習，相信大家對分塊查找這一高效的查找算法有了全面的理解。讓我們回顧一下本文的核心要點：

核心知識點回顧

分塊查找的精髓在于巧妙結合了順序查找和折半查找的優點：

• "塊內無序、塊間有序"的設計理念

• 通過索引表搭建快速定位，通過塊內順序查找保證靈活性

• 兩種實現方式：邏輯分配（保持原數組）和物理分配（重排數組）

關鍵收獲：

• 當塊大小s=√n時，平均查找長度達到最優值√n+1

• 索引表可選用順序查找或折半查找，適應不同場景需求

• 在動態數據環境下，分塊查找展現出獨特的優勢

實際應用價值

分塊查找不僅在理論學習中具有重要意義，在實際開發中也有著廣泛應用：

• 數據庫索引的底層原理

• 文件系統的目錄結構設計

• 大規模素材的分片處理

• 實時系統中的快速檢索

期待與您互動

如果本文對您有協助，歡迎：

• 點贊 - 您的認可是我持續創作的最大動力

• 收藏 ? - 方便日后隨時查閱復習

• 關注 ? - 獲取更多數據結構與算法的精彩內容

• 轉發 - 分享給更多要求的小伙伴

• 評論 - 留下您的寶貴意見和學習心得

您還希望了解哪些查找算法或數據結構的深度解析？在評論區告訴我，我會根據大家的需求安排后續的創作計劃！

學習之路，你我同行。 讓我們在算法的世界里繼續探索，下期再見！?