基本演算法介紹-搜尋
搜尋演算法（Searching Algorithms）
【定義】
尋找目標的方法稱為搜尋法
【目的】
為什麼我們需要搜尋演算法？在圖書館找一本書、在Google上鍵入搜尋內容，或者在電腦上搜尋檔案時， 電腦要處理如此大量的資料，因此我們需要快速的演算法來幫助我們快速找到資料。 沒有它們， 在大量資料中，這將花費很長時間。因此，學習搜尋演算法可以來幫助更了解資訊科學的概念。
思考問題:在日常生活中何時會用的搜尋演算法?
【生活應用】
體驗活動1
1.蠟筆小新抽鬼牌下載
2.找盒子(Searching Box)：
part1
遊戲解說:
您可能已經注意到，遊戲框中的數字是隨機排列的，這表示找到目標數字基本上是靠運氣的！ 您可能在第一次嘗試時就已經找到了它，或者，如果您不太幸運，則可能必須先查看幾乎所有盒子才能找到它。 這看起來似乎不是一件壞事，因為您有足夠的生命來看所有盒子，但請想像若是有1,000盒子，或者更糟的是1,000,000盒子！ 翻遍所有盒子可能要花很長時間，而且可能永遠找不到目標編號。
part2
思考問題:
現在，下一場遊戲略有不同。 您的生命值減少了，這使事情變得更具挑戰性，但是這次箱子內的數字井井有條。 編號最小的框在最左側，編號最大的框在最右側。 讓我們看看是否可以找到所有目標數字而不會耗盡生命值
【資訊科學應用】
體驗活動2
1.終極猜數字遊戲
資料來源:Animations from Grokking Algorithms
2.海戰棋遊戲
二.體驗活動說明
基本搜尋演算法
在不同的資料結構上有各式各樣不同的搜尋演算法，在國中部分針對陣列( Array ) 做搜尋。高中大學則是應用在圖形 ( Graph )或樹 ( Tree )，討論的就是深度搜尋跟廣度搜尋。
搜尋演算法應用 -資訊安全名畫神偷(Art Thief )遊戲
循序搜尋法(Sequential Search)與二分搜尋法（Binary Search）之搜尋效率比較
資料來源:心淵大大
資料引用:108課綱康軒第二章
*進階研究
參考資料
https://sites.google.com/a/ntjh.ntct.edu.tw/105pljh/home/searchalgorithm
https://csfieldguide.org.nz/en/chapters/algorithms/searching/
循序(線性)搜尋法(Sequential(Linear) )Search程式實作
圖片引用:108課綱高中一年級高中資訊科技科友出版社
一.程式執行結果(搜尋1-100的數(可重複))
參考程式下載(不一定要和老師一樣.可以有自己的邏輯思維)
二.循序搜尋演算法實作
實作步驟:
1.建立data清單隨機產生10個(1-100)的數字
2.點貓咪開始搜尋.詢問使用者(輸入)要搜尋的數字範圍(1-100).呼叫執行循序搜尋函數
3.撰寫循序搜尋函數
(1)變數初始化
key(答案)
i位置(索引值)
found(找到與否的flag(旗標).1代表找到.0代表沒找到)
(2)重複清單長度次
(3)如果key(答案)=清單的第i位置(索引值)那麼
說出"找到了.在第i位置(索引值)位置"
found設為1
否則i位置(索引值)改變1.繼續尋找清單內的元素
(4)如果found為0那麼
說出"找不到你要的數字"
三.測試程式
1.輸入清單的第1項數字.貓咪要說"找到了,在第1個位置"
2.輸入清單的第10項數字.貓咪要說"找到了,在第10個位置"
3.輸入清單內沒有的數字.貓咪要說"找不到你要的數字"
四.程式碼觀摩
(1)
(2)
思考問題:
觀察上述兩種寫法有何不同?哪一種寫法比較優?你有其他想法嗎?
*進階研究
二分搜尋法原理解說影片
(1)Scratch程式實作
(2)Python程式實作(高中)
https://colab.research.google.com/drive/1-Y-YZ36xL3L2Tra8Zr-eAs-_FoTrDZ
圖片引用:108課綱高中一年級高中資訊科技科友出版社
.gif)
