HW2-敘述何謂二分搜尋法? 自己設一個數列來做舉例 並告訴我二分搜尋怎麼使用 還有何謂二元樹(binary tree)? 並舉例作圖~

何謂二分搜尋法?

       用以搜尋已排序的一串資料。其原理為將欲搜尋的值，與所有資料的中間值(中位數)做比對。

舉例:我用[ 10 12 15 14 13 11 16]來做二分搜尋法，先利用各種排序法(快速排序，選擇排序，泡沫排序，循序排序...)將資料做大小排列成[ 10 11 12 13 14 15 16 ]

 我要如何找到12這個數字呢?

      由於中間值13大於搜索值12。因此我們可以知道，在13之後的資料皆大於搜索值12，接著，由於13之前資料中的中間值1小大於搜索值12。我們可以知道，在11之前的資料皆小於搜索值12。最後我們就找到了搜索值12。

     圖:

          第一次[ 10 11 12 13 14 15 16 ]

          第二次[ 10 11 12 ]

          第三次[ 12 ]

在二元樹中 我該怎麼在樹中查到我要的數字呢?

      (1)從樹的樹根 (root) 開始，和每個節點比較

    (2)如果現在這個數字，比現在這個節點的數字小，往左邊的子樹 (sub-tree) 走，否則就往右走

       (3)重覆步驟(2) ，比較新遇到的節點，和現在輸入的數字。如果已經走到樹的結尾，就停止。

        圖:                         13

                               11          15

                         10     12  14      16