一、順序查找?

條件：無序或有序隊列。?

原理：按順序比較每個元素，直到找到關鍵字為止。?

時間復雜度：O(n)?

二、二分查找（折半查找）?

條件：有序數組?

原理：查找過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束； 如果某一特定元素大于或者小于中間元素，則在數組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。 如果在某一步驟數組為空，則代表找不到。 這種搜索算法每一次比較都使搜索范圍縮小一半。?

時間復雜度：O(logn)?

三、二叉排序樹查找?

條件：先創建二叉排序樹： 1. 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 2. 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； 3. 它的左、右子樹也分別為二叉排序樹。?

原理： 在二叉查找樹b中查找x的過程為： 1. 若b是空樹，則搜索失敗，否則： 2. 若x等于b的根節點的數據域之值，則查找成功；否則： 3. 若x小于b的根節點的數據域之值，則搜索左子樹；否則： 4. 查找右子樹。?

時間復雜度：O(log2(n))?

四、哈希表法（散列表）?

條件：先創建哈希表（散列表）?

原理：根據鍵值方式(Key Value)進行查找，通過散列函數，定位數據元素。

時間復雜度：幾乎是O(1)，取決于產生沖突的多少。?

五、分塊查找?

思想：順序查找和二分查找的結合。

原理：將n個數據元素"按塊有序"劃分為m塊（m ≤ n）。 每一塊中的結點不必有序，但塊與塊之間必須"按塊有序"；即第1塊中任一元素的關鍵字都必須小于第2塊中任一元素的關鍵字； 而第2塊中任一元素又都必須小于第3塊中的任一元素，……。 然后使用二分查找及順序查找。

時間復雜度：介于O(n) 和O(logn)之間。

總結

以上是生活随笔為你收集整理的常用查找算法（顺序、折半、二叉树、哈希、分块）介绍的全部內容，希望文章能夠幫你解決所遇到的問題。

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