平均查找長度

為確定記錄在查找表中的位置，需和給定值進行比較的關鍵字個數的期望值稱為查找算法在查找 成功時的 平均查找長度()，ASL成功。

對於含有n個數據元素的查找表，查找成功的平均查找長度為：ASL=∑PiCi (i=1,2,3,…,n),可以簡單以數學上的期望來這么理解。其中：Pi 為查找表中第i個數據元素的機率，Ci為找到第i個數據元素時已經比較過的次數。

在查找表中查找不到待查元素，但是找到待查元素應該在表中存在的位置的平均查找次數稱為查找 不成功時的 平均查找長度，不成功。