基本演算法介紹--搜尋3

基本演算法介紹-搜尋3

搜尋演算法（Searching Algorithms）

【定義】

尋找目標的方法稱為搜尋法

【目的】

為什麼我們需要搜尋演算法？在圖書館找一本書、在Google上鍵入搜尋內容，或者在電腦上搜尋檔案時，電腦要處理如此大量的資料，因此我們需要快速的演算法來幫助我們快速找到資料。沒有它們，在大量資料中，這將花費很長時間。因此，學習搜尋演算法可以來幫助更了解資訊科學的概念。

思考問題:在日常生活中何時會用的搜尋演算法?

【生活應用】

一.體驗活動

1.找盒子(Searching BOX)：

進行以下遊戲一並完成解題

part1

遊戲解說:

　　您可能已經注意到，遊戲框中的數字是隨機排列的，這表示找到目標數字基本上是靠運氣的！您可能在第一次嘗試時就已經找到了它，或者，如果您不太幸運，則可能必須先查看幾乎所有盒子才能找到它。這看起來似乎不是一件壞事，因為您有足夠的生命來看所有盒子，但請想像若是有1,000盒子，或者更糟的是1,000,000盒子！翻遍所有盒子可能要花很長時間，而且可能永遠找不到目標編號。現在，下一場遊戲略有不同。您的生命減少了，這使事情變得更具挑戰性，但是這次箱子內的數字將井井有條。編號最小的框在最左側，編號最大的框在最右側。讓我們看看是否可以找到所有目標數字而不會耗盡生命...

part2

思考問題:

如果您已經玩完了整個遊戲（並希望找到了所有目標數字！），您可能已經注意到，即使您在遊戲的第二部分中的可用生命減少，並且有很多可以搜索的盒子，您仍然能夠找到目標號碼。為什麼會這樣呢？

2.多啦ㄟ夢猜大雄數學考幾分遊戲

宜蘭國中李寬亮老師設計

3. 名畫神偷(Art Thief )遊戲

二.體驗活動說明

1.線性搜尋法（Linear search ）或循序搜尋法(Sequential Search)

由於遊戲第一局中的盒子是隨機排列(沒有排序的)，所以實際上您沒有什麼策略可以找到目標編號，只是簡單地逐個打開盒子直到找到目標編號。這本質上是線性搜尋法（有時稱為循序序搜尋）。簡單來說，線性搜尋法如下：
檢查列表中的第一個項目是否是您要搜尋的項目，如果它是您要尋找的項目，則完成。如果不是您要搜尋的項目，請繼續檢查下一個項目。繼續檢查項目，直到找到要搜尋的項目。如果使用此算法，您可能會很幸運在初次嘗試時就找到了要尋找的東西，但是，如果您真的很不幸，則可能必須先遍歷列表中的所有內容，然後才能找到合適的對象

2.二分搜尋法（Binary search）

是一種在有序(排序)陣列中搜尋某一特定元素的搜尋演算法

在盒子搜尋遊戲的第二部分中，盒子是有排序的，這意味著您在搜尋目標編號時會變得更加聰明，並且您可能一直在使用二分搜尋而沒有意識到！如果您在每個步驟上都使用二分搜尋，那麼您一定會有足夠的生命找到目標編號！
二元搜尋如下：
檢查列表中心的項目，然後將其與您要搜索的內容進行比較。如果大於要查找的項目，則可以忽略列表中大於該項目的所有項目（如果列表從最小到最大，則意味著可以忽略中心右側的所有項目項目）。如果較小，則可以忽略列表中所有小於該中心項目的項目。然後，在列表的其餘一半上重複該算法，檢查列表的中間並選擇二分之一(一半)，直到找到要搜尋的項目。

原理解說影片