2017年9月29日 星期五

演算法:二分搜尋法( Binary Search Algorithm )

最近想著怎麼教國中生二分搜尋法(Binary Search),就找到在可汗學院上的猜數字遊戲,就將此網頁的教學觀念改成在下的版本。

可汗學院上的猜數字有兩題,一題是猜1到16的數字:


一題是猜1到300的數字:

根據以上的範例,就找了這個網頁 http://ftp.phjh.tc.edu.tw/~klychen/Research/FinalNumber/ChooseNum.php 給學生試試,並詢問學生底下兩個問題:

  1. 能在幾次內猜中?
  2. 用了什麼策略?

之後再解釋怎麼做才能保證在10次內猜中 1 到 1000 之間的數字,並解釋什麼是二分搜尋法,
結果發現其實有些國中生早就有怎麼解題的觀念了,只是不知道這個觀念是二分搜尋法的基礎,二分搜尋法適合在已經排序好的資料,而且也是個類似 divide and conquer 的方法。