1、查找的基本概念

查找也即檢索。

文件：由記錄組成的集合，即含有大量數據的元素線性組合而成。
記錄：由若干數據項組成的數據元素，這些數據項也常稱作記錄中的數據域，用以表示某個狀態的物理意義。
關鍵字：用以區分文件中記錄的數據項的值。若此關鍵字可以惟一地標識一個記錄，則稱此關鍵字為主關鍵字。也就是說，對于不同的記錄，其對應的主關鍵字的值均不相同。若數據元素只有一個數據項，其關鍵字即為該數據元素的值。

查找是指根據給定的某個值，確定關鍵字值，查詢確定關鍵字值與給定值相等的記錄在文件中的位置。它是程序設計中一項重要的基本技術。查找的結果有兩種情況：若在文件中找到了待查找的記錄，則稱查找成功，這時可以得到該記錄在文件中的位置，或者得到該記錄中其他的信息；若在文件中沒有找到所需要的記錄，則稱查找不成功或查找失敗，這時，相應的查找算法給出查找失敗的信息，同時也得到記錄插入文件的位置。

查找可分為靜態查找和動態查找兩種，在查找過程中不修改查找表的長度和表中內容的方法稱作靜態查找，反之稱作動態查找。

2、查找算法的評價指標

平均查找長度（ASL）： 在查找的過程中，一次查找的長度是指需要比較的關鍵字次數，而平均查找長度則是所有查找過程中進行關鍵字的比較次數的平均值。

• n：記錄的個數
• pi：查找第i個記錄的概率 ( 通常認為pi =1/n )
• ci：找到第i個記錄所需的比較次數

3、靜態查找表

3.1 順序查找

1）應用范圍

順序表或線性鏈表表示的靜態查找表

2）順序表的表示

typedef struct { //查找表的數據結構ElemType *R; //元素存儲空間基址int length; //表的長度 }SSTable;

3）性能分析

• 查找成功時的平均查找長度(設表中各記錄查找概率相等)：ASL=(1+2+ … +n)/n =(n+1)/2
• 查找不成功時的平均查找長度：ASL =n+1

4）特點

• 算法簡單，對表結構無任何要求（順序和鏈式）。
• n很大時，平均查找長度較大，查找效率較低。
• 改進措施：非等概率查找時，可按照查找概率進行排序。

3.2 折半查找

1）算法思想：

設表長為n，low、high和mid分別指向待查元素所在區間的上界、下界和中點，k為給定值：

• 初始時，令low=1, high=n, mid=(low+high)/2；

• 讓k與mid指向的記錄比較：若k = R[mid].key，查找成功若k < R[mid].key，則high=mid-1若k > R[mid].key，則low=mid+1；

• 重復上述操作，直至low>high時，查找失敗。

2）折半查找的性能分析：

• 查找過程：每次將待查記錄所在區間縮小一半，比順序查找效率高，時間復雜度O(log2 n)
• 適用條件：采用順序存儲結構的有序表，不宜用于鏈式結構

3.3 分塊查找（塊間有序，塊內無序）

分塊有序，即分成若干子表，要求每個子表中的數值都比后一塊中數值小（但子表內部未必有序）。 然后將各子表中的最大關鍵字構成一個索引表，表中還要包含每個子表的起始地址（即頭指針）。

1）分塊查找過程：

• 對索引表使用折半查找法（因為索引表是有序表）
• 確定了待查關鍵字所在的子表后，在子表內采用順序查找法（因為各子表內部是無序表）

2）分塊查找優缺點：

• 優點：插入和刪除比較容易，無需進行大量移動。
• 缺點：要增加一個索引表的存儲空間并對初始索引表進行排序運算。
• 適用情況：若線性表既要快速查找又經常動態變化，則可采用分塊查找

3）分塊查找的性能分析

分塊查找的平均長度為索引查找和塊內查找的平均長度值和。設索引查找和塊內查找的平均長度分別為 L1，L2，則分塊查找的平均查找長度為

4、B樹和B+樹

B樹是一種多路平衡查找樹，它的每一個結點最多包含 m 個孩子，m 被稱為 B 樹的階。

B樹主要應用于文件系統以及部分數據庫索引，比如 MongoDB。

而大部分關系型數據庫，比如 Mysql，則使用 B+ 樹作為索引。

一個m階的B樹具有如下幾個特征：

• 樹中每個結點至多有 m 棵子樹，即至多含有 m-1 個關鍵字。
• 若根節點不是終端結點，則至少有兩顆子樹。
• 除根節點外的所有非葉結點至少有?m/2?棵子樹，即至少有?m/2? - 1 個關鍵字。
• 所有的葉子結點都位于同一層，且不帶信息。
• 每個節點中的元素從小到大排列。

B樹的高度

若 n ≥ 1，則對任意一棵包含 n 個關鍵字、高度為 h 、階數為 m 的 B 樹。

h ≥ logm(n+1)，h ≤ log?m/2?((n+1)/2)+1。

一個m階的B+樹具有如下特征：

• 每個分支最多有 m 棵子樹。
• 非葉根節點至少有兩顆子樹，其他每個分支結點至少有 ?m/2? 棵子樹。
• 結點子樹個數與關鍵字個數相等。
• 所有分支結點中僅包含它的各個子結點（即下一級的索引塊）中關鍵字的最大值及指向其子結點的指針。
• 所有的葉子結點中包含了全部元素的信息，及指向含這些元素記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序鏈接。
• 在 B+ 樹中，葉結點包含了全部關鍵字，即在非葉結點中出現的關鍵字也會出現在葉結點中；而在 B 樹中，葉結點包含的關鍵字和其他結點包含的關鍵字是不重復的。

B+樹的優勢：

• 單一節點存儲更多的元素，使得查詢的IO次數更少。
• 所有查詢都要查找到葉子節點，查詢性能穩定。
• 所有葉子節點形成有序鏈表，便于范圍查詢。

5、哈希表的查找

1）基本思想：記錄的存儲位置與關鍵字之間存在對應關系：

優點：查找速度極快，為O(1)，查找效率與元素個數n無關。

裝填因子

總結

以上是生活随笔為你收集整理的查找算法详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。