演講人數(shù)據(jù)結(jié)構(gòu)與算法之查找介紹課件目錄01查找概述03樹(shù)形查找02線性查找04哈希查找1查找概述查找的定義查找是指在數(shù)據(jù)集合中尋找滿足特定條件的數(shù)據(jù)元素查找的目的是為了獲取所需信息或執(zhí)行特定操作查找方法包括順序查找、二分查找、哈希查找等查找效率是衡量查找算法優(yōu)劣的重要指標(biāo)查找應(yīng)用場(chǎng)景數(shù)據(jù)庫(kù)查詢：根據(jù)關(guān)鍵字查找數(shù)據(jù)記錄搜索引擎：根據(jù)關(guān)鍵詞查找網(wǎng)頁(yè)信息字典查詢：根據(jù)單詞查找釋義和例句電話簿查詢：根據(jù)姓名或電話號(hào)碼查找聯(lián)系人信息圖書(shū)館圖書(shū)查詢：根據(jù)書(shū)名或作者查找圖書(shū)信息地圖查詢：根據(jù)地名或坐標(biāo)查找地理位置社交軟件好友查找：根據(jù)用戶名或昵稱(chēng)查找好友購(gòu)物網(wǎng)站商品查找：根據(jù)商品名稱(chēng)或描述查找商品信息音樂(lè)播放器歌曲查找：根據(jù)歌曲名稱(chēng)或歌手查找歌曲信息文件系統(tǒng)文件查找：根據(jù)文件名或內(nèi)容查找文件信息查找的分類(lèi)順序查找：從列表的一端開(kāi)始，逐個(gè)比較元素，直到找到目標(biāo)元素哈希查找：通過(guò)計(jì)算元素的哈希值，直接定位到目標(biāo)元素的位置樹(shù)查找：通過(guò)構(gòu)建樹(shù)形結(jié)構(gòu)，實(shí)現(xiàn)快速查找二分查找：適用于有序列表，通過(guò)不斷將列表分為兩部分，直到找到目標(biāo)元素索引查找：通過(guò)建立索引表，快速定位到目標(biāo)元素的位置圖查找：適用于圖數(shù)據(jù)結(jié)構(gòu)，通過(guò)遍歷圖來(lái)找到目標(biāo)元素2線性查找順序查找順序查找是一種簡(jiǎn)單的查找方法，適用于線性表和數(shù)組。順序查找的基本思想是：從線性表的一端開(kāi)始，逐個(gè)檢查每個(gè)元素，直到找到目標(biāo)元素或查找失敗。順序查找的時(shí)間復(fù)雜度為O(n)，其中n為線性表的長(zhǎng)度。順序查找的優(yōu)點(diǎn)是簡(jiǎn)單易實(shí)現(xiàn)，適用于數(shù)據(jù)量較小的情況。折半查找1原理：將查找范圍分為兩部分，每次查找都排除一半2時(shí)間復(fù)雜度：O(logn)3優(yōu)點(diǎn)：查找速度快，適用于有序數(shù)據(jù)集4缺點(diǎn)：需要數(shù)據(jù)集有序，不適用于無(wú)序數(shù)據(jù)集插值查找原理：根據(jù)查找關(guān)鍵字與查找表中最大、最小值的關(guān)系，估算查找位置優(yōu)點(diǎn)：對(duì)于均勻分布的數(shù)據(jù)，查找效率較高適用場(chǎng)景：數(shù)據(jù)量較大，且數(shù)據(jù)分布均勻的情況缺點(diǎn)：對(duì)于非均勻分布的數(shù)據(jù)，查找效率較低030102043樹(shù)形查找二叉查找樹(shù)概念：一種特殊的二叉樹(shù)，每個(gè)節(jié)點(diǎn)都包含一個(gè)鍵值，左子樹(shù)的鍵值小于根節(jié)點(diǎn)，右子樹(shù)的鍵值大于根節(jié)點(diǎn)性質(zhì)：二叉查找樹(shù)是平衡的，即左右子樹(shù)的高度差不超過(guò)1操作：插入、刪除、查找等操作可以在O(logN)的時(shí)間復(fù)雜度內(nèi)完成應(yīng)用：二叉查找樹(shù)廣泛應(yīng)用于數(shù)據(jù)庫(kù)、文件系統(tǒng)、編譯器等系統(tǒng)中，以提高查找效率。平衡二叉樹(shù)01平衡二叉樹(shù)是一種特殊的二叉樹(shù)，具有平衡性02平衡二叉樹(shù)的每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，且左右子樹(shù)的高度差不超過(guò)103平衡二叉樹(shù)的查找效率較高，時(shí)間復(fù)雜度為O(logN)04平衡二叉樹(shù)可以通過(guò)旋轉(zhuǎn)操作來(lái)保持平衡性B樹(shù)和B+樹(shù)STEP4STEP3STEP2STEP1B樹(shù)：一種平衡多路查找樹(shù)，每個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)鍵值，每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)。B+樹(shù)：一種改進(jìn)的B樹(shù)，所有葉子節(jié)點(diǎn)在同一層，每個(gè)葉子節(jié)點(diǎn)存儲(chǔ)一個(gè)鍵值和一個(gè)指向其父節(jié)點(diǎn)的指針。B樹(shù)和B+樹(shù)的區(qū)別：B+樹(shù)更適合磁盤(pán)存儲(chǔ)，因?yàn)槊總€(gè)葉子節(jié)點(diǎn)都在同一層，可以減少磁盤(pán)I/O次數(shù)。B樹(shù)和B+樹(shù)的應(yīng)用：廣泛應(yīng)用于數(shù)據(jù)庫(kù)索引、文件系統(tǒng)等場(chǎng)景。4哈希查找哈希函數(shù)的設(shè)計(jì)01哈希函數(shù)應(yīng)具有較好的散列性，以避免沖突02哈希函數(shù)應(yīng)具有較低的計(jì)算復(fù)雜度，以提高查找效率03哈希函數(shù)應(yīng)具有較好的抗碰撞性，以減少?zèng)_突04哈希函數(shù)應(yīng)具有較好的均勻性，以避免數(shù)據(jù)分布不均勻哈希沖突的解決開(kāi)放地址法：尋找下一個(gè)空閑位置01鏈地址法：使用鏈表存儲(chǔ)沖突的元素02再哈希法：使用另一個(gè)哈希函數(shù)計(jì)算新的哈希值03公共溢出區(qū)法：將所有沖突的元素存儲(chǔ)在一個(gè)公共溢出區(qū)中04哈希查找的性能分析時(shí)間復(fù)雜度：O(1)，查找速度非?？?101020304空間復(fù)雜度：O(n)，需