【概述】

查找是在具相同類型的記錄構成的集合中，找出滿足給定條件的記錄，給定的查找條件是多樣的，為便于討論，將查找條件限制為 “匹配”，即查找關鍵碼等于給定值的記錄。

在查找中，常將數據元素稱為記錄，將可以標識一個記錄的某個數據項稱為關鍵碼，關鍵碼的值稱為鍵值，若關鍵碼可以唯一標識一個記錄，則稱其為主關鍵碼，反之，稱為次關鍵碼。

【查找分類】

1.靜態查找

靜態查找是指不涉及插入、刪除操作的查找，其在查找不成功時，只返回一個不成功的標志，查找的結果不改變查找集合。

其適用于以下兩種情景：

• 查找集合一旦生成，只對其進行查找
• 對查找集合經過一段時間查找后，集中地進行插入、刪除等操作

2.動態查找

動態查找是指涉及插入、刪除操作的查找，其在查找不成功時，需要將查找的記錄插入到查找集合中，查找的結果可能會改變查找集合。

其適用于查找與插入、刪除操作在同一階段進行的情景。

【查找結構】

一般而言，各種數據結構都會涉及到查找操作，但在某些應用中，查找操作是最主要的操作，為提高查找效率，需要設計專門的查找結構。

常見的查找結構有：

• 線性表：適用于靜態查找，主要采用順序查找、折半查找等
• 樹表：適用于動態查找，主要采用二叉排序樹查找等
• 散列表：靜態查找、動態查找均適用，主要采用哈希查找

【查找的性能】

查找算法的基本操作通常是將記錄的關鍵碼與給定值進行比較，其運行時間主要消耗在關鍵碼的比較上，因此應以關鍵碼的比較次數來度量查找算法的時間性能，其時間復雜度是問題規模 n 和待查關鍵碼在查找集合中的位置 k 的函數，記為：T(n,k)

對于查找算法，關心的是其整體性能，故將關鍵碼的比較次數的數學期望值定義為平均查找長度（ASL）。

對于查找成功的情況，有：，其中，Pi 為查找表中第 i 個記錄的概率，Ci 為找到第 i 個記錄所需的關鍵碼的比較次數。

對于查找不成功的情況，平均查找長度為查找失敗對應的關鍵碼的比較次數。

【分類】

1.線性表的查找技術

1）順序查找：點擊這里

2）二分查找：點擊這里

3）插值查找：點擊這里

4）斐波那契查找：點擊這里

2.樹表的查找技術

1）二叉排序樹：點擊這里

2）平衡二叉樹（AVL 樹）：點擊這里

3.哈希查找：點擊這里

?

?

?

總結

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

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