基本演算法介紹-搜尋
搜尋(search) 演算法
搜尋(search) 演算法:在大量資料中找出目標資料的演算法
(1)日常生活的應用
例如從通訊錄找出某好友的電話號碼、利用電話號碼或身分證，找出會員資料或是從字典中查詢某一個單字
(2)搜尋(search) 演算法種類
最常用的搜尋演算法有
循序搜尋法(Sequential Search)
二分搜尋法(Binary Search)
牛刀小試1-搜尋演算法種類
解說:
循序搜尋法(Sequential Search)
範例
(1)Pokemons 這一排櫃子裡有4隻神奇寶貝，假設每個櫃子的門都被關上，我們事前也不知道各個神奇寶貝的位置，這時如果想要知道「比獸」神奇寶貝在哪裡時，我們第一個想到的方法會是什麼呢？
最直觀地想，我們會從第一個櫃子開始試，一次開一個櫃子，直到找到「比獸」為止。像這樣的搜尋方法，就是最經典簡單的「簡易搜尋」。
(2)假設原始資料有：5、17、33、41、55、61 、80這 7 個隨機數字，搜尋的目標資料是33，因為原始資料只有 7 個數字，所以你能夠一眼就看到33 在原始資料的第 3 筆，但是如果資料量暴增到 1000 個，你就得要從解決問題的過程中找出規則，將其發展成一套搜尋演算法，而這套演算法適用於各種大小的資料量與各種不同的目標資料。
思考問題
想想看此類循序搜尋法有何特色呢?
說明
1.比運氣
2.速度慢(當 n 值很大的時候，例如 1,000,000 筆資料，平均搜尋的就要 50 萬次， 搜尋時間就相對較長)
二分搜尋法（Binary Search）
資料來源:Animations from Grokking Algorithms
解說
玩1到100的終極密碼，一個個從頭慢慢猜最壞要猜100次。但用二分搜尋法（Binary Search）每次從中剖半，留下正確的部分再剖半，7次就能猜出來了。當放大到40億個數字的終極密碼，一個個從頭慢慢猜最壞要猜40億次；後者只要32次就能猜出來了。
如果搜尋的數列已經有排序，應該儘量利用它們已排序的特性，以減少搜尋比對的次數，這是搜尋的基本原則，二分搜尋法是這個基本原則的代表。
範例
假設原始資料有：5、17、33、41、55、61 、80這 7 個隨機數字，在二分搜尋法中，我們先打開最中間的櫃子，發現裡面的數字是 41。因為 55 比 41 大，因此我們知道從一號櫃到三號櫃都不會有 55，接下來只需要檢查五號櫃到七號櫃。 同樣的邏輯，我們打開剩下三個可能性中最中間的櫃子，發現六號櫃裡面的數字是 61，因為 61 比 55 大，我們可以知道七號櫃的數字一定也比 55 大，得知 55 一定就在五號櫃之中。
牛刀小試2-搜尋法視覺化工具
牛刀小試3-猜謎遊戲
思考問題
想想看二分搜尋法有何特色呢?
說明:
1.速度快
2.要排序
搜尋方法的時間複雜度(花費時間)-高中課綱
循序(簡易)搜尋，我們可以知道最壞的情況就是剛好七個步驟（要找的數字是 80 ）
二分搜尋法，我們可以先練習去計算各種情況需要的步驟，而最終的答案如下表：
從上表我們可以發現，二分搜尋法最慘最慘，也只需要三個步驟。 推廣到有 n 個櫃子時，我們可以發現：二分搜尋法在每進行一個步驟時，就可以排除掉一半的可能性。每次都能減少一半，因此二分搜尋法最糟最糟也只需要以 2 為底的 log n 個步驟就能完成。當資料量很大時(100萬筆資料)時，此方法搜尋速度就會很快
搜尋程式實作篇(老師可依學生程度實作.此為高一課綱)
循序搜尋法(Sequential Search)(此為高一課綱.但簡單可實作)
http://usr.nkust.org/2018/06/12/scratch-sequential-search/
參考積木
二分搜尋法（Binary Search）實作篇(老師可依學生程度實作.此為高一課綱)
體驗SCRATCH利用二分搜尋 binary search製作猜數字遊戲
https://scratch.mit.edu/projects/89598637/#editor
體驗micro:bit 製作的二分搜尋 binary search製作猜數字遊戲
http://glglace.blogspot.tw/2017/10/1160-microbit-7-binary-search.html
參考積木
牛刀小試4-海戰棋遊戲
解說
https://sites.google.com/a/ntjh.ntct.edu.tw/105pljh/home/searchalgorithm
參考網站