1.3.2　查找

查找問題（searching problem）就是在給定的集合（或者是多重集，它允許多個元素具有相同的值）中找一個給定的值［我們稱之為查找鍵（search key）］。有許多查找算法可供選擇，其中既包括直截了當的順序搜索，也包括效率極高但應用受限的折半查找，還有那些將原集合用另一種形式表示以方便查找的算法。最后一類算法對于現實應用具有特別重要的價值，因為它們對于大型數據庫的信息存取來說是不可或缺的。

對于查找來說，也沒有一種算法在任何情況下都是最優的。有些算法比其他算法速度快，但需要較多的存儲空間；有些算法速度非?？欤珒H適用于有序的數組。和排序算法不同，查找算法沒有穩定性問題，但會發生其他問題。具體來說，如果應用里的數據相對于查找次數頻繁變化，查找問題就必須結合另外兩種操作一起考慮：在數據集合中添加和刪除元素的操作。在這種情況下，必須仔細選擇數據結構和算法，以便在各種操作的需求之間達到一個平衡。而且，對于用于高效查找（以及添加和刪除）的特大型數據集合來說，如何組織其結構是一個不同尋常的挑戰，而這對實際應用具有非常重要的意義。