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初版 

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

 

 

圖書館週報

《生命的躍升》 214王俊力 推薦

「生命」到底從何而來?又為何而來?是困擾人類許久的問題。缺乏完善科學技術的古人往往透過超自然力量尋求解釋,「造物主」的概念也隨之產生。直到19世紀才由達爾文提出有系統的演化論,但這只是個開端。催動演化的原因與演化的方向至今仍充滿爭議。《生命的躍升》作者透過十個演化史上的關鍵佐以分子生物學證據,讓演化不只是「物競天擇,適者生存」,更是有系統的生命樂章!

詳細閱讀

書籍的秩序:歐洲的讀者、作者與圖書館(14-18世紀) 324李怡坤 推薦

 本書由歷史學者侯瑞.夏提葉的三篇論文構成,分別是〈讀者社群〉、〈作者的形象〉、〈沒有牆的圖書館〉,旨在探討14世紀至18世紀之間,歐洲人如何因應印刷術對於書籍製作和文學生產造成的衝擊。

詳細閱讀

王丹回憶錄──從六四到流亡 (123宛靖 推薦)

在過去四十多年的人生歷程中,我經歷過中國七零年代末的巨大轉折、八零年代理想主義的高昂;我參與過八九民運這樣天地、泣鬼神的壯舉,我也在二十幾歲就承受了黑牢的煎熬;我見識過人生的險惡,我也體會過生活的溫暖;我在中國成長,在美國完成學業,在台灣工作;我是政治反對派,我也是一個文學愛好者和創作者,我更是一個感情豐富的人。我將要在此講述的這所有理想,都見證了一個人,一個時代,一個國家。──王丹

詳細閱讀

愛閱滿天星

319王廷鎧《24個比利》

News image

本書屬於一部精神疾病患者的傳記,內容記述此位患者─比利的成長經歷、治療過程與互動言行,我認為此書最令我驚訝的是它所包含的一字一句皆很細膩流暢,劇情連貫且因為描寫手法使其劇情極為豐富生動,絲毫不像一般的志人記錄,反倒像是一本文情並茂的小說......

詳細閱讀

知識充電站

淺論二分搜尋法

News image

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

詳細閱讀

線上資料庫選粹

原子樂高

News image

樂高積木這種小小的塑膠組合方塊,啟發了許多世代的傑出人才。這種小方塊可做出時髦汽車的樣式、精細的城堡,以及效果遠超過所有方塊組合、令人讚歎的各種創作。現在,新型樂高積木將啟發新一代的材料科學家,而這種樂高積木就是原子尺度的「構件」......

詳細閱讀