❶ 有贊搜索引擎實踐(演算法篇)
註：轉自於 有贊
在上篇文章(工程篇)中, 我們介紹了有贊搜索引擎的基本框架. 搜索引擎主要3個部件構成. 第一, hadoop集群, 用於生成大規模搜索和實時索引; 第二, ElasticSearch集群, 提供分布式搜索方案; 第三, 高級搜索集群, 用於提供商業搜索的特殊功能.
商業電商搜索由於搜索的特殊性, 獨立的ElasticSearch集群是無法滿足多樣的演算法需求的, 我們在搜索的各個部件上都有相應的演算法插件, 用於構建商業電商搜索引擎的演算法體系.
創建索引過程從原始數據創建倒排索引的過程. 這個過程中我們對商品(doc)進行分析, 計算商品靜態分, 並對商品進行相似度計算. 商品的靜態分對於提升搜索引擎質量起到至關重要的作用, 相當於網頁搜索的pagerank, 想像一下如果沒有pagerank演算法, 網頁搜索的質量會有多麼差. 在電商搜索中, 最常見的問題是相似商品太多, 必須在建立索引過程中就對商品間的相似度進行預計算, 以便在檢索過程中進行有效去重.
創建索引的過程如下.
step 1. 計算每個doc的靜態分
step 2. 計算兩兩doc的相似度
step 3. 根據相似度和其他信息對數據進行分庫
step 4. 建立ES索引
檢索過程是搜索引擎接收用戶的query進行一系列處理並返回相關結果的過程. 商業搜索引擎在檢索過程中需要考慮2個因素: 1) 相關性 2) 重要性.
相關性是指返回結果和輸入query是否相關, 這是搜索引擎基本問題之一, 目前常用的演算法有BM25和空間向量模型. 這個兩個演算法ElasticSearch都支持, 一般商業搜索引擎都用BM25演算法. BM25演算法會計算每個doc和query的相關性分, 我們使用Dscore表示.
重要性是指商品被信賴的程度, 我們應該吧最被消費之信賴的商品返回給消費者, 而不是讓消費之自己鑒別. 尤其是在商品充分競爭的電商搜索, 我們必須賦予商品合理的重要性分數, 才能保證搜索結果的優質. 重要性分, 又叫做靜態分, 使用Tscore表示.
搜索引擎最終的排序依據是:
Score = Dscore * Tscore
即綜合考慮靜態分和動態分, 給用戶相關且重要的商品.
檢索的過程大致抽象為如下幾個步驟.
step 1. 對原始query進行query分析
step 2. 在as中根據query分析結果進行query重寫
step 3. 在as中使用重寫後的query檢索es
step 4. 在es查詢過程中根據靜態分和動態分綜合排序
step 5. 在as中吧es返回的結果進行重排
step 6. 返回結果
下面幾章闡述幾個重點技術.
在電商搜索引擎裡面商品的靜態分是有網頁搜索裡面的pagerank同等的價值和重要性, 他們都是doc固有的和查詢query無關的價值度量. pagerank通過doc之間的投票關系進行運算, 相對而言商品的靜態分的因素會更多一些. 商品靜態計算過程和pagerank一樣需要解決如下2個問題: 1. 穩定性. pagerank可以保證一個網站不會因為簡單鏈接堆砌可以線性提升網站的排名. 同樣, 商品靜態分的計算不可以讓商品可以通過增加單一指標線性增加分值(比如刷單對搜索引擎的質量的影響).
2. 區分度. 在保證穩定性的基礎上商品靜態分要有足夠的區分度可以保證同樣搜索的條件下, 排在前面的商品的質量比排在後面的商品的質量高.
我們假設商品的靜態分有3個決定性因素, 1.下單數, 2. 好評率 3. 發貨速度
靜態分我們使用Tsocre表示, Tscore可以寫成如下形式:
Tscore = a * f(下單數) + b * g(好評率) + c * h(發貨速度)
a,b,c是權重參數, 用於平衡各個指標的影響程度. f,g,h是代表函數用於把原始的指標轉化成合理的度量.
首先, 我們需要尋找合理的代表函數.
z-score 標准化方法
這種方法非常不穩定, 假設一個奇異點是第二大的值的1000倍, 會讓大部分的值都集中在0~0.01, 同樣失去了歸一化的目的.
(圖三: log-zscore歸一化)
最後, 選擇合適的權重 經過log-zscore歸一化以後, 我們基本上吧f,g,h的表示的代表函數說明清楚. Tscore = a f(下單數) + b g(好評率) + c*h(發貨速度), 下一步就是確定a,b,c的參數. 一般有兩個方法:
a) 專家法. 根據我們的日常經驗動態調整權重參數;
b) 實驗法. 首先在專家的幫助下賦一個初始值, 然後改變單一變數的方法根據abtest的結果來動態調整參數.
商品標題去重在電商搜索中起到重要作用, 根據數據, 用戶通過搜索頁購買商品80%選擇搜索的前4頁. 商品標題的重復會導致重要的頁面沒有含金量, 極大降低了搜索的購買率.
舉個例子:
Title1:美味/香蕉/包郵/廣東/高州/香蕉/banana//無/催熟劑/
Title2:美味/香蕉/廣東/高州/香蕉//非/粉蕉/包郵/
首先, 進行特徵向量化
這里用到 "bag of word" 技術, 將詞彙表作為空間向量的維度, 標題的每個term的詞頻作為這個feature的值. 以這個例子來說. 這個詞彙的維度為: 美味(0), 香蕉(1), 包郵(2), 廣東(3), 高州(4), banana(5),無(6), 催熟劑(7),非(8),粉蕉(9) 位置: 0,1,2,3,4,5,6,7,8,9
Title1: 1,2,1,1,1,1,1,1,0,0
Title2: 1,2,1,1,1,0,0,0,1,1
這個每個title都用一個固定長度的向量表示.
再次, 計算兩兩相似度
相似度一般是通過計算兩個向量的距離實現的, 不失一般性, 在這里我們使用1-cosine(x,y)來表示兩個向量的距離. 這是一個"All Pair Similarity"的問題, 即需要兩兩比較, 復雜度在O(n^2). 在商品量巨大的時候單機很難處理. 我們給出兩種方法用於實現"All Pair Similarity".
方法一: spark的矩陣運算.
方法二: map-rece 線性方法. 這個方法參考論文"Pairwise Document Similarity in Large Collections with MapRece". 可以實現幾乎線性的時間復雜度. 相對於矩陣運算在大規模(10億以上)pair similarity 運算上面有優勢. 這個方法簡單的描述如下: 首先, 按照倒排索引的計算方式計算每個term到doc的映射. 比如3個doc:
轉化為倒排格式, 這個需要一次mapper rece
然後, 對於value只有一個元素的過濾掉, 對於value大於2個doc的兩兩組合:
最後, 對於輸出進行聚合,value為重復次數和兩個doc乘積開根號的比.
對於2個title1, title2, 如果X(title1, title2) > 0.7 則認為title1和title2相似, 對於相似的兩個doc, 靜態分大的定義為主doc, 靜態分小的定義為輔doc. 主doc和輔doc分別建庫.
區別於網頁搜索(網頁搜索直接將輔doc刪除), 我們將主doc和輔doc分別建庫. 每一次搜索按比例分別搜主庫和輔庫, 並將結果融合返回. 這樣可以保證結果的多樣性.
店鋪去重和商品標題去重有點不同. 由於電商特定場景的需要, 不希望搜索結果一家獨大, 這樣會引發強烈的馬太效應. 店鋪去重不能使用如上的方法進行. 因為上面的方法的主要依據是文本相似, 在結果都相關的前提下, 進行適當的取捨. 但是店鋪去重不是這樣的特性.
設想一下, 如果我們根據店鋪是否相同, 把同一店鋪的商品分到主庫和從庫中, 如下圖所示.
A和B代表不同的店鋪.
在搜索香蕉的時候, 的確可以控制A店鋪結果的數量, 但是在搜索"梨"的時候就錯誤的吧B店鋪的梨排在前面了(假設A:梨比B:梨靜態分高).
搜索的過程每個桶平均分攤搜索任務的25%, 並根據靜態分合並成一頁的結果. 這樣同一保證結果的相對順序, 又達到了店鋪去重的目的.
如上圖所示, 搜索"香蕉", 雖然A店鋪有10個滿足需求的結果, 但是每頁搜索醉倒只有5個結果可以展示.
上面介紹了幾個建立索引過程中幾項技術, 檢索過程中的關鍵技術有很多. 其中最著名的是query分析技術. 我們使用的query分析技術主要包括核心詞識別, 同義詞拓展, 品牌詞識別等等. query分析技術大部分都是NLP研究范圍, 本文就不詳細闡述很多理論知識. 我們重點介紹同義詞拓展技術. 這個技術一般都需要根據自己的商品和和用戶日誌特定訓練, 無法像分詞技術和品牌詞識別一樣有標準的庫可以適用.
同義詞拓展一般是通過分析用戶session日誌獲取. 如果一個用戶輸入"蘋果手機"沒有得到想要的結果, 他接著輸入"iphone", 我們在"蘋果手機"和"iphone"之間創建一個轉移關系. 基於統計, 我們可以把用戶query創建一個相互聯系的權重圖.
用戶輸入query "蘋果手機", 根據query分析, "蘋果手機"有 "iphone" 0.8, "iphone 6" 0.5 兩個同義詞. 0.8和0.5分別表示同義的程度. 我們想要"蘋果手機", "iphone", "iphone 6" 3個query同時輸入, 並且按照同義的程度對不同的query賦予不同的權重. ElasticSearch提供的BoostingQuery可以支持這個需求. 參考: https://www.elastic.co/guide/en/elasticsearch/guide/current/ boosting query_clauses.html
原始query:
改寫後的Query
其他比如核心詞識別, 歧義詞糾正等方法差不多, 本文不做詳細闡述.
商業電商搜索演算法另外兩個重要技術, 一個是類目體系建立和應用,另一個是個性化技術. 這個兩項技術我們還處在探索階段. 類目體系我們主要使用機器學習的方法進行訓練, 個性化主要通過用戶畫像進行Query改寫來實現. 等我們上線有效果在與大家分享.
搜索演算法是一個非常值得一個電商產品持續投入的技術. 一方面我們技術人員要有良好的技術背景, 可以借鑒很多成熟的技術, 避免重復造輪子; 另一方面, 每個產品的搜索都有自身的特點, 需要深入研究產品的特性給出合理的解決方案. 本文給出的案例都具有代表性, 靈活的運用搜索的各方面的技術. 另外, 商業搜索非常看重投入產出比, 我們也需要在眾多方案中尋找捷徑. 比如我們在做類目體系時候, 沒有投入大量的人力資源用於標注數據, 而是通過爬蟲爬取其他電商的數據進行參考, 從而節省了80%的人力資源. 由於筆者能力有限, 文中的方案不保證是問題的最優解, 如果有指正, 請聯系筆者( hongbin@youzan.com ).
❷ A*演算法現實應用的實際意義
A*演算法在人工智慧中是一種典型的啟發式搜索演算法，為了說清楚A*演算法，我看還是先說說何謂啟發式演算法。
一、何謂啟發式搜索演算法
在說它之前先提提狀態空間搜索。狀態空間搜索，如果按專業點的說法就是將問題求解過程表現為從初始狀態到目標狀態尋找這個路徑的過程。通俗點說，就是在解一個問題時，找到一條解題的過程可以從求解的開始到問題的結果（好象並不通俗哦）。由於求解問題的過程中分枝有很多，主要是求解過程中求解條件的不確定性，不完備性造成的，使得求解的路徑很多這就構成了一個圖，我們說這個圖就是狀態空間。問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結果。這個尋找的過程就是狀態空間搜索。
常用的狀態空間搜索有深度優先和廣度優先。廣度優先是從初始狀態一層一層向下找，直到找到目標為止。深度優先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標為止。這兩種演算法在數據結構書中都有描述，可以參看這些書得到更詳細的解釋。
前面說的廣度和深度優先搜索有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分大，且不預測的情況下就不可取了。他的效率實在太低，甚至不可完成。在這里就要用到啟發式搜索了。
啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無畏的搜索路徑，提到了效率。在啟發式搜索中，對位置的估價是十分重要的。採用了不同的估價可以有不同的效果。我們先看看估價是如何表示的。
啟發中的估價是用估價函數表示的，如：
f(n) = g(n) + h(n)
其中f(n)是節點n的估價函數，g(n)實在狀態空間中從初始節點到n節點的實際代價，h(n)是從n到目標節點最佳路徑的估計代價。在這里主要是h(n)體現了搜索的啟發信息，因為g(n)是已知的。如果說詳細點，g(n)代表了搜索的廣度的優先趨勢。但是當h(n)>>g(n)時，可以省略g(n),而提高效率。這些就深了，不懂也不影響啦！我們繼續看看何謂A*演算法。
二、初識A*演算法
啟發式搜索其實有很多的演算法，比如：局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。象局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了其他的節點，可能也把最好的節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點（除非該節點是死節點），在每一步的估價中都把當前的節點和以前的節點的估價值比較得到一個「最佳的節點」。這樣可以有效的防止「最佳節點」的丟失。那麼A*演算法又是一種什麼樣的演算法呢？其實A*演算法也是一種最好優先的演算法。只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值，h'(n)是n到目標的最斷路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明應用這樣的估價函數是可以找到最短路徑的，也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。哈！你懂了嗎？肯定沒懂！接著看！
舉一個例子，其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先演算法是一種可採納的。實際也是。當然它是一種最臭的A*演算法。
再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由於實時性的問題，h(n)的信息越多，它的計算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。
❸ 演算法在實際生活中的應用
求解問題類的、機械的、統一的方法，它由有限多個步驟組成，對於問題類中的每個給定的具體問題，機械地執行這些步驟就可以得到問題的解答。演算法的這種特性，使得計算不僅可以由人，而且可以由計算機來完成。用計算機解決問題的過程可以分成三個階段：分析問題、設計演算法和實現演算法。
中國古代的籌算口決與珠算口決及其執行規則就是演算法的雛形,這里,所解決的問題類是算術運算。古希臘數學家歐幾里得在公元前3世紀就提出了一個演算法,來尋求兩個正整數的最大公約數，這就是有名的歐幾里得演算法,亦稱輾轉相除法。中國早已有「算術「、「演算法」等詞彙，但是它們的含義是指當時的全部數學知識和計算技能,與現代演算法的含義不盡相同。英文algorithm(演算法)一詞也經歷了一個演變過程，最初的拼法為algorism或algoritmi,原意為用阿拉伯數字進行計算的過程。這個詞源於公元 9世紀波斯數字家阿爾·花拉子米的名字的最後一部分。
在古代，計算通常是指數值計算。現代計算已經遠遠地突破了數值計算的范圍,包括大量的非數值計算,例如檢索、表格處理、判斷、決策、形式邏輯演繹等。
在20世紀以前，人們普遍地認為，所有的問題類都是有演算法的。20世紀初，數字家們發現有的問題類是不存在演算法的,遂開始進行能行性研究。在這一研究中,現代演算法的概念逐步明確起來。30年代，數字家們提出了遞歸函數、圖靈機等計算模型，並提出了丘奇－圖靈論題（見可計算性理論），這才有可能把演算法概念形式化。按照丘奇-圖靈論題,任意一個演算法都可以用一個圖靈機來實現，反之，任意一個圖靈機都表示一個演算法。
按照上述理解，演算法是由有限多個步驟組成的，它有下述兩個基本特徵：每個步驟都明確地規定要執行何種操作；每個步驟都可以被人或機器在有限的時間內完成。人們對於演算法還有另一種不同的理解，它要求演算法除了上述兩個基本特徵外,還要具有第三個基本特徵:雖然有些步驟可能被反復執行多次，但是在執行有限多次之後，就一定能夠得到問題的解答。也就是說，一個處處停機（即對任意輸入都停機）的圖靈機才表示一個演算法，而每個演算法都可以被一個處處停機的圖靈機來實現
演算法分類
演算法可大致分為基本演算法、數據結構的演算法、數論與代數演算法、計算幾何的演算法、圖論的演算法、動態規劃以及數值分析、加密演算法、排序演算法、檢索演算法、隨機化演算法、並行演算法。
演算法可以宏泛的分為三類：
有限的，確定性演算法 這類演算法在有限的一段時間內終止。他們可能要花很長時間來執行指定的任務，但仍將在一定的時間內終止。這類演算法得出的結果常取決於輸入值。
有限的，非確定演算法 這類演算法在有限的時間內終止。然而，對於一個（或一些）給定的數值，演算法的結果並不是唯一的或確定的。
無限的演算法 是那些由於沒有定義終止定義條件，或定義的條件無法由輸入的數據滿足而不終止運行的演算法。通常，無限演算法的產生是由於未能確定的定義終止條件。演算法特徵一個演算法應該具有以下五個方面的重要特徵：1、輸入。一個演算法有零個或多個輸入，以刻畫運算對象的初始情況。例如，在歐幾里得演算法中，有兩個輸入，即m和n。2、確定性。演算法的每一個步驟必須要確切地定義。即演算法中所有有待執行的動作必須嚴格而不含混地進行規定，不能有歧義性。例如，歐幾里得演算法中，步驟1中明確規定「以m除以n，而不能有類似以m除n以或n除以m這類有兩種可能做法的規定。3、有窮性，一個演算法在執行有窮步滯後必須結束。也就是說，一個演算法，它所包含的計算步驟是有限的。例如，在歐幾里得演算法中，m和n均為正整數，在步驟1之後，r必小於n，若r不等於0，下一次進行步驟1時，n的值已經減小，而正整數的遞降序列最後必然要終止。因此，無論給定m和n的原始值有多大，步驟1的執行都是有窮次。4、輸出。演算法有一個或多個的輸出，即與輸入有某個特定關系的量，簡單地說就是演算法的最終結果。例如，在歐幾里得演算法中只有一個輸出，即步驟2中的n。5、能行性。演算法中有待執行的運算和操作必須是相當基本的，換言之，他們都是能夠精確地進行的，演算法執行者甚至不需要掌握演算法的含義即可根據該演算法的每一步驟要求進行操作，並最終得出正確的結果。演算法的描述1、用自然語言描述演算法前面關於歐幾里得演算法以及演算法實例的描述，使用的都是自然語言。自然語言是人們日常所用的語言，如漢語、英語、德語等。使用這些語言不用專門訓練，所描述的演算法也通俗易懂。2、用流程圖描述演算法在數學課程里，我們學習了用程序框圖來描述演算法。在程序框圖中流程圖是描述演算法的常用工具由一些圖形符號來表示演算法。3、用偽代碼描述演算法偽代碼是用介於自然語言和計算機語言之間的文字和符號來描述演算法的工具。它不用圖形符號，因此，書寫方便、格式緊湊，易於理解，便於向計算機程序設計語言過度。
❹ 搜索演算法的應用案例
(1)題目：黑白棋游戲
黑白棋游戲的棋盤由4×4方格陣列構成。棋盤的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。這16枚棋子的每一種放置方案都構成一個游戲狀態。在棋盤上擁有1條公共邊的2個方格稱為相鄰方格。一個方格最多可有4個相鄰方格。在玩黑白棋游戲時，每一步可將任何2個相鄰方格中棋子互換位置。對於給定的初始游戲狀態和目標游戲狀態，編程計算從初始游戲狀態變化到目標游戲狀態的最短著棋序列。
(2)分析
這題我們可以想到用深度優先搜索來做，但是如果下一步出現了以前的狀態怎麼辦？直接判斷時間復雜度的可能會有點大，這題的最優解法是用廣度優先搜索來做。我們就可以有初始狀態按照廣度優先搜索遍歷來擴展每一個點，這樣到達目標狀態的步數一定是最優的（步數的增加時單調的）。但問題是如果出現了重復的情況我們就必須要判重，但是樸素的判重是可以達到狀態數級別的，其實我們可以考慮用hash表來判重。
Hash表：思路是根據關鍵碼值進行直接訪問。也就是說把一個關鍵碼值映射到表中的一個位置來訪問記錄的過程。在Hash表中，一般插入，查找的時間復雜度可以在O（1）的時間復雜度內搞定。對於這一題我們可以用二進制值表示其hash值，最多2^16次方，所以我們開個2^16次方的表記錄這個狀態出現沒有，這樣可以在O（1）的時間復雜度內解決判重問題。
進一步考慮：從初始狀態到目標狀態，必定會產生很多無用的狀態，那還有什麼優化可以減少這時間復雜度？我們可以考慮把初始狀態和目標狀態一起擴展，這樣如果初始狀態的某個被擴展的點與目標狀態所擴展的點相同時，那這兩個點不用擴展下去，而兩個擴展的步數和也就是答案。
上面的想法是雙向廣度優先搜索：
就像圖二一樣，多擴展了很多不必要的狀態。
從上面一題可以看到我們用到了兩種優化方法，即Hash表優化和雙向廣搜優化。一般的廣度優先搜索用這兩個優化就足以解決。
❺ 信息發展從而衍生各種數據演算法，大數據又是如何運用在我們的生活中呢
網路時代大多都是依靠各種數據演算法而運行的，也有不少的數據演算法是從發展中不斷衍生的，大家最為熟悉的就是大數據。人人都處於大數據時代，只要使用網路必然就接觸過大數據，因為它實際上就滲透在我們生活的每個角落。隨著信息發展從而衍生了各種數據演算法，那麼大數據又是如何運用在我們的生活中呢？
當我們在使用各種軟體的時候，其實就是在被試探，刷視頻時長時間停留在某個視頻，購物時經常查看某個價格區間的物品，那麼下次打開軟體時推送的就會依照上一次的使用習慣進行推送。所以大數據時代為人們增添了不少便利，更是成為了大家的及時雨。
❻ 查找演算法的作用
查找就是在一個數據集合里查找到你需要的數據，查找演算法就是在查找過程中使用的演算法。查找演算法有好多，最基礎的就是線性表查找。
因為提到了演算法，所以需要注意的是時間復雜度跟空間復雜度，進而涉及到數據的存儲方式，比如數組，鏈表，矩陣，樹，圖等等數據結構，這些數據結構可以幫助你降低演算法的復雜度。
如果有興趣，隨便找本數據結構書翻翻，裡面或多或少都會有講解。用關鍵字標識一個數據元素，查找時根據給定的某個值，在表中確定一個關鍵字的值等於給定值的記錄或數據元素。在計算機中進行查找的方法是根據表中的記錄的組織結構確定的。順序查找也稱為線形查找，從數據結構線形表的一端開始，順序掃描，依次將掃描到的結點關鍵字與給定值k相比較，若相等則表示查找成功；若掃描結束仍沒有找到關鍵字等於k的結點，表示查找失敗。二分查找要求線形表中的結點按關鍵字值升序或降序排列，用給定值k先與中間結點的關鍵字比較，中間結點把線形表分成兩個子表，若相等則查找成功；若不相等，再根據k與該中間結點關鍵字的比較結果確定下一步查找哪個子表，這樣遞歸進行，直到查找到或查找結束發現表中沒有這樣的結點。分塊查找也稱為索引查找，把線形分成若干塊，在每一塊中的數據元素的存儲順序是任意的，但要求塊與塊之間須按關鍵字值的大小有序排列，還要建立一個按關鍵字值遞增順序排列的索引表，索引表中的一項對應線形表中的一塊，
