logologo_right

library

開館時間
.學期中週一至週五
 上午8:00~下午5:30
.國定假日及例假日不開館
.寒暑假開館時間另行公布
淺論二分搜尋法


20150513s.jpg當要在以排序的陣列中搜尋元素時,二分搜尋法(binarysearch)是有效率的演算法之一。其最基本的原理為藉由不斷的將含有搜尋目標的陣列分成兩部分,使可能範圍縮小到只剩一個......

二分搜尋法最常用在搜尋有序陣列裡的元素。舉例來說,第谷第二星表之中包含了2,539,913顆恆星。假如你現在想要在表中以名稱搜尋某一恆星,如果程式從頭按序搜索每一個資料內容(循序),在最差的情況之下,電腦必須檢測2,539,913次。但如果資料已經以恆星第一個字母排列,用二分搜尋法的話,最多只要檢測22次。若是有N筆資料,在最差的情況下,二分搜尋法的時間複雜度為(log2N+ 1),且資料量越大效能越好(在計算機中,演算法的時間複雜度是一個函數,為該演算法的運行時間)。
讓我用猜數字遊戲來做說明。首先設定遊戲範圍為1到100。假如你猜25,我就會說"太小"(圖一);你猜81,我會說"太大"(圖二)。有此可知,除非你讀書壓力太大想耍白癡的話,你下一次應該會猜26到80。這時就可以套用二分搜尋法,猜兩數的中點:(26+80)/2=53。接下來我會告訴你53太大了(圖三)。這樣你就可以把53到80的數字刪掉,留下26到52(圖四),也就是原範圍的一半。以此類推,你將可以快速得到答案。

2015051301.jpg 
 2015051302.jpg

中文概述:
1.設 low = m 而 high = n.
2.猜high 和low的中間值並取整數。
3.假如你猜到了,就可以停止。
4.假如猜得太小, 令 low為比原猜測數字還大的數字。假如猜得太大, 令 high為比原猜測數字還小的數字。
5.回到步驟2


以上內容摘自可汗學院,由213班 劉昶樂 同學整理並精心挑選推薦以下好書與大家分享 ~!! 


 

館  藏  選 介

(請點選書名連結本館書目,歡迎同學借閱~)

2015051303.jpg 演算法:認識程式設計的基礎 寫給初學者的「演算法」入門書
杉浦賢 著  鍾沛君譯 瑞昇出版/2012初版 

深入淺出的解說,適合普羅大眾閱讀 搭配彩色圖解與生動比喻,專業知識輕鬆學 從「何謂演算法、何謂程式」為起始,到排序及檢索、測量演算法效率、其它演算法……均有詳細解說,內容涵蓋基礎到專業知識。
   以上圖片與簡介摘自博客來網路書店
   

 

 

愛閱滿天星

304蔡融兒《白雪公主殺人事件》

歷史有真相嗎?真相到底是什麼?

詳細閱讀