资料的搜寻.ppt

資料的搜尋 搜尋的基本概念 循序搜尋法(Sequential Search) 二元搜尋法(Binary Search) 內插搜尋法(Interpolation Search) 影響搜尋時間長短的主要因素 演算法 資料儲存的方式 資料儲存的結構 搜尋的分類 從資料檔案中，尋找符合某特定條件的記錄。」這個動作就叫搜尋。而用來搜尋的條件就稱為「鍵值」，例如我們在電話簿中找某人的電話，那麼這個人的姓名就成為在電話簿中搜尋電話資料的鍵值。 若依資料量大小來區分，搜尋可分為： 1.內部搜尋：資料量較小的檔案，可以直接全部載入記憶體中進行搜尋。 2.外部搜尋：資料量大的檔案，無法一次載入記憶體處理，而需使用到輔助記憶體來分次處理。 搜尋的技巧 除了上述的分類方式外，我們還能以搜尋過程中被搜尋的表格或資料是否異動，區分為靜態搜尋(Static Search)及動態搜尋(Dynamic Search)。 靜態搜尋是指資料在搜尋過程中，該搜尋資料不會有增加、刪除、或更新等行為，例如符號表搜尋就屬於一種靜態搜尋。 動態搜尋則是指所搜尋的資料，在搜尋過程中會經常性地增加、刪除、或更新。 循序搜尋法(Sequential Search) 循序搜尋又稱線性搜尋，是一種最簡單的搜尋法。它的方法是將資料一筆一筆的循序搜尋，這很像在走訪陣列一般的從頭找到尾，所以不管資料是否經過排序，都是得從頭到尾走訪過一次。此法的優點是檔案在搜尋前不需作任何的處理與排序，缺點為搜尋速度較慢。 循序搜尋法分析 分析: 時間複雜度：如果資料沒有重覆，找到資料就可中止搜尋的話，在最差狀況是未找到資料，需作n次比較，時間複雜度為O(n)。 在平均狀況下，假設資料出現的機率相等，則需(n+1)/2次比較。 當資料量很大時，不適合使用循序搜尋法。但如果預估所搜尋的資料在檔案前端則可以減少搜尋的時間。 二元搜尋法(Binary Search) 如果要搜尋的資料已經排序好，則可使用二分法來進行搜尋。二分法是將資料分割成兩等份，再比較鍵值與中間值的大小，如果鍵值小於中間值，可確定要找的資料在前半段的元素，如此分割數次直到找到為止。 二元搜尋法分析 時間複雜度：因為每次的搜尋都會比上一次少一半的範圍，最多只需要比較[log2n]+1或[log2(n+1)]，時間複雜度為O(log n)。 二分法必須事先經過排序，且資料量必須能直接在記憶體中執行。 此法適合用於不需增刪的靜態資料。 循序搜尋法與二元搜尋法的優缺點 循序搜尋法 優點：?這個搜尋方最簡單，資料無需事先排序 。 缺點：?搜尋速度較慢，比較沒有效率，除非事先知道所搜尋的資料位置在前端。 二元搜尋法 優點：?和循序搜尋法相較起來，其搜尋速度較快。 缺點：必須事先將資料排序好，且儲存裝置必須能夠直接存取，例如磁帶就不適合二元搜尋法。 內插搜尋法(Interpolation Search) 內插搜尋法又叫做插補搜尋法，是二元搜尋法的改良版。它是依照資料位置的分佈，利用公式預測資料的所在位置，再以二分法的方式漸漸逼近。使用內插法是假設資料平均分佈在陣列中，而每一筆資料的差距是相當接近或有一定的距離比例。其內插法的公式為： Mid=low + (( key - data[low] ) / ( data[high] - data[low] ))* ( high - low ) 插補搜尋法的步驟 key是要尋找的鍵，data[high]、data[low]是剩餘待尋找記錄中的最大值及最小值，對資料筆數為n，插補搜尋法的步驟如下： 1.將記錄由小到大的順序給予1,2,3...n的編號 2.令low=1，high=n 3.當lowhigh時，重複執行步驟4及步驟5 4.令Mid=low + (( key - data[low] ) / ( data[high] -data[low] ))* ( high - low ) 5. 若keykey[Mid]且high≠Mid-1則令high=Mid-1 若key＝key[Mid]表示成功搜尋到鍵值的位置 若keykey[Mid]且low≠Mid+1則令low=Mid+1 插補搜尋法分析 1.一般而言，內插搜尋法優於循序搜尋法，而如果資料的分佈愈平均，則搜尋速度愈快，甚至可能第一次就找到資料。此法的時間複雜度取決於資料分佈的情況而定，平均而言優於O(log n)。 2.使用內插搜尋法資料需先經過排序。 搜尋 (Searching) 搜尋 (Searching)