close
Q: 敘述何謂二分搜尋法?自己設一個數列來做舉例，並告訴我二分搜尋怎麼使用。
還有何謂二元樹(binary tree)?並舉例作圖~
(若有程式碼的貼上後 最好在附上compiler的結果給我看(圖片))
Ans 1 何謂二分搜尋法？－
從已排列的數列的中間開始搜尋，如果這個數小於我們所搜尋的數，由於數列已排序，
則該數左邊的數一定都小於要搜尋的對象，所以無需浪費時間在左邊的數；
如果搜尋的數大於所搜尋的對象，則右邊的數無需再搜尋，直接搜尋左邊的數。
Ans 2 如何使用二分搜尋法（假設）？－
二分搜尋法中，將數列不斷的分為兩個部份，每次從分割的部份中取中間數比對，
例如要搜尋18於以下的數列，首先中間數索引為(0+9)/2 = 4（索引由0開始）：
｛2 9 13 18 26 34 45 51 59 65｝
索引 0 1 2 3 4 5 6 7 8 9
由於26大於18，所以轉搜尋左邊的數列：
｛2 9 13 18｝ 26 34 45 51 59 65
由於9小於18，再搜尋右邊的數列，這次就找到所要的數了：
2 9｛13 18｝ 26 34 45 51 59 65
Ans 3 何謂二元樹(binary tree)？－
在資料結構中，二元樹是指樹中的每一個「節點」（Nodes）最多只能擁有2個子節點，即分支度小於或等於2。
二元樹的節點個數是一個有限集合，或是沒有節點的空集合。
二元樹的節點可以分成兩個沒有交集的子樹，稱為「左子樹」（Left Subtree）和「右子樹」（Right Subtree），
且左子樹的值不會大於節點的值，右子樹的值不會小於結點的值。
Ex:圖片
而假若我們今天要從上圖搜尋3，從最上結點開始判斷，
比5小，往左子樹判斷，比4小，在往左子樹判斷，比2大，往右子樹即可尋得。
最後總結兩者做個比較，像老師課堂上說過的：
當資料型態構造簡單(排序)的時候，搜尋資料所使用的演算法(二元搜尋法)是困難的；
當資料型態構造困難(二元樹)，則使用的搜尋演算法(直接搜尋法)就簡單多了，
而我們寫成是寧願資料結構完整複雜，也不要演算法複雜！
全站熱搜
留言列表
東海大學大一資料夾 (0)
