線性查找

線性查找又稱順序查找，是一種最簡單的查找方法，它的基本思想是從第一個記錄開始，逐個比較記錄的關鍵字，直到和給定的K值相等，則查找成功；若比較結果與檔案中n個記錄的關鍵字都不等，則查找失敗。

基本介紹

• 中文名：線性查找
• 外文名：linear search
• 定     義：又稱為順序查找
• 套用學科：計算機技術方法術語
• 縮寫：LS
• 元素：順序查找

概念

線性查找又稱順序查找，是一種最簡單的查找方法，它的基本思想是從第一個記錄開始，逐個比較記錄的關鍵字，直到和給定的K值相等，則查找成功；若比較結果與檔案中n個記錄的關鍵字都不等，則查找失敗。

查找是對具有相同屬性的數據元素（記錄）的集合（數據對象）進行的，稱之為表或檔案，也稱字典。對表的查找，若僅對表進行查找操作，而不能改變表中的數據元素，為靜態查找；對表除了進行查找操作外，還可能對表進行插入或刪除操作，則為動態查找。

工作原理

例如r[i].key表示數據元素i中的關鍵字項。在流程圖中的循環迴路上要進行兩次比較，即對數據元素的關鍵字項比較和對循環次數的判斷。為了提高運算速度，可以作如下的改進：

在原表長n的基礎上增加一個元素n+1，將K值送入此元素的關鍵字項中，這樣在循環迴路上只要進行一次比較，我們把第n+1個記錄稱為“監視哨”。這樣當n很大時幾乎可以節省一半時間。

在順序查找中，在找到第i個記錄時，給定值K和記錄中的關鍵字進行了i次比較。

由於平均查找長度與表長度n成線性關係，因此當n較大時，順序查找的效率較低。但順序查找算法比較簡單，且對順序表的存儲結構沒有限制，既可以用向量作存儲結構也可以用鍊表作存儲結構。