前言

今天要來介紹循序搜尋法與二元搜尋法，這兩者有什麼差別呢？一起來看看吧

生活常識

你有去書局買過壁報紙嗎？如果朋友拿了一張藍色小紙片，請你到書局幫忙添購同顏色的紙張，而你第一次買也不清楚到底是要買深一點的藍色，還是淺一點的藍色，那麼書局的色卡可能是你的好幫手，因為色卡大多是按照顏色與深淺下去排列，只要與你手上的顏色相比對就知道要買哪一種顏色，而你會怎麼比對呢？從頭到尾逐一比對直到找到為止，還是從色卡的中間的顏色然後每次都跳好幾個格子開始比？

圖片來源:https://unsplash.com/photos/zeKekb76k-s

或是像是看牙齒做齒模的時候，醫生跟護士也會使用模型逐一比對患者的牙齒顏色

圖片來源:https://www.pexels.com/zh-tw/photo/3845548/

如果面對的是一堆雜亂無章沒有排序也沒有整理過的螺絲，如果朋友請你幫他找出一根某種類型的螺絲，你又會怎麼找呢

專業知識 - 循序搜尋法 Sequentail Search / 線性搜尋法 Linear Search

由螺絲的例子來看，在找東西之前，若能將資料先排序好(像是色卡的例子)，會有利於資料的尋找，有關於排序的內容可以參考前面幾天的文章，若資料沒有排序又想找資料的話，那會推薦你使用循序搜尋法，一個一個慢慢找，找到天荒地老XD，這方法還需要我推薦嗎，感覺幼稚園小朋友都知道這個方法XD

循序搜尋法是一種非常簡單的演算法，就是從頭到尾逐一比較每一個資料，資料小時還可行，但資料量大時，則不推薦此種作法，因為真的會花費非常多的時間

例子

有一數列：1, 9, 2, 8, 6, 3, 5, 4，要找 3 在哪個位置，則從第 1 個位置開始逐一往後面搜尋，最後在第 6 個位置找到數值 3 ，是不是很曠日廢時

分析

• 最壞的情況
  資料有 n 筆，找到最後一筆才找到想找的資料，則時間複雜度為O(n)

• 最好的情況
  資料有 n 筆，找到第一筆剛好就是想找的資料，則時間複雜度為O(1)

專業知識 - 二元搜尋法 Binary Search / 二分搜尋(Half-Interval Search)

二元搜尋法又稱二搜尋法，是針對已經排序好的資料進行搜尋，二元搜尋法會取出數列的中間值與想要找的數值進行比對，並以這個中間值分區為前半部與後半部，會有三種情況需要判斷
1.想要找的數值等於中間值，則結束搜尋
2.想要找的數值大於中間值，而表示要找的資料會落在後半部，則繼續將取後半部的中間值繼續比對
3.想要找的數值小於中間值，而表示要找的資料會落在前半部，則繼續將取前半部的中間值繼續比對

例子

有一數列：1, 22, 32, 48, 56, 63, 47, 82, 94，共 9 個數值，由小到大排列，要找 82 在哪裡

• 步驟一
  將資料切一半之前要找到中間值，9 / 2 會得到 4.5 ，有小數點我們就無條件進位，剛好就能選到位置 5 正中間的位置，然後比對位置 5 的 56 與 82，發現 82 > 56，則可推得 82 是在後半部

• 步驟二
  繼續針對後半部搜尋，後半部剩下 4 個數值，4 / 2 = 2，這邊可以發現其實沒辦法選到正中間，因為 4 是偶數，這時候就看要選位置 2 或 3 都可以，接著將 位置 2 的 77 與 82 比較，發現 82 > 75

• 步驟三
  比對後半段，這時候資料只剩下兩筆，2/2 = 1，挑選位置 1 的 82 與 82 比對，發現 82 = 82，所以搜尋結束，在 1, 22, 32, 48, 56, 63, 47, 82, 94 的數列中，在位置 8 找到了 82

分析

• 最壞的情況
  資料有 n 筆，每次資料都會切一半，往需要前半部或後半部找，時間複雜度為O(log n)

• 最好的情況
  資料有 n 筆，第一次的中間值剛好就是想找的資料，則時間複雜度為O(1)

今日小結

資料小量時可使用循序搜尋法，資料量大時建議使用二元搜尋法

今日謎題

小美的忘記了他自己的腳踏車鎖的密碼，他回家翻閱密碼鎖的說明書時，發現了一個神祕的圖片，請問你能幫忙小美打開腳踏車鎖嗎？密碼鎖為 4 位數字

昨日解謎

謎題說明：因為元素表雖然有編號 1~118，但我們並不懂元素跟數字的對應關係，只能使用循序搜尋法，用眼睛掃瞄並逐一的去確認每個元素的英文命名是不是與蒙娜麗莎的諧音相似，然後就會找到 Li 、 Na 與 Mo，調整一下順序與蒙娜麗莎名字相同，再找到該元素的編號，即可獲得 5 位數密碼：42113，你答對了嗎？