1.3.2　查找

查找問(wèn)題（searching problem）就是在給定的集合（或者是多重集，它允許多個(gè)元素具有相同的值）中找一個(gè)給定的值［我們稱(chēng)之為查找鍵（search key）］。有許多查找算法可供選擇，其中既包括直截了當(dāng)?shù)捻樞蛩阉鳎舶ㄐ蕵O高但應(yīng)用受限的折半查找，還有那些將原集合用另一種形式表示以方便查找的算法。最后一類(lèi)算法對(duì)于現(xiàn)實(shí)應(yīng)用具有特別重要的價(jià)值，因?yàn)樗鼈儗?duì)于大型數(shù)據(jù)庫(kù)的信息存取來(lái)說(shuō)是不可或缺的。

對(duì)于查找來(lái)說(shuō)，也沒(méi)有一種算法在任何情況下都是最優(yōu)的。有些算法比其他算法速度快，但需要較多的存儲(chǔ)空間；有些算法速度非常快，但僅適用于有序的數(shù)組。和排序算法不同，查找算法沒(méi)有穩(wěn)定性問(wèn)題，但會(huì)發(fā)生其他問(wèn)題。具體來(lái)說(shuō)，如果應(yīng)用里的數(shù)據(jù)相對(duì)于查找次數(shù)頻繁變化，查找問(wèn)題就必須結(jié)合另外兩種操作一起考慮：在數(shù)據(jù)集合中添加和刪除元素的操作。在這種情況下，必須仔細(xì)選擇數(shù)據(jù)結(jié)構(gòu)和算法，以便在各種操作的需求之間達(dá)到一個(gè)平衡。而且，對(duì)于用于高效查找（以及添加和刪除）的特大型數(shù)據(jù)集合來(lái)說(shuō)，如何組織其結(jié)構(gòu)是一個(gè)不同尋常的挑戰(zhàn)，而這對(duì)實(shí)際應(yīng)用具有非常重要的意義。