擁抱「資料結構」的「演算法」(25) - 循序搜尋法與二元搜尋法

 

前言

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

生活常識

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



圖片來源: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，你答對了嗎？



留言

張貼留言

這個網誌中的熱門文章

CPE 一顆星選集題目說明與解答 - Java 筆記與心得分享

以下是自己的 CPE 一顆星選集 解題紀錄 (共有 49 題) 每次考試都會從一顆星選集中抽 1 提出來考 算是比較能把握的部分，重點筆記整理如下 內容包含題目說明、程式碼、註解說明、解答、考古題統計(下方土黃色日期) 解題使用的程式語言是  JAVA  目前有提供 10 題的試閱 另有提供完整 49 題的完整解答 ( pdf 檔 )， 共 305 頁， 售價 $399 元 ， 若有需要請來信購買 greens2314@gmail.com 推薦閱讀： 建議熟讀 java 基本觀念，與使用 eclipse 練習， 等熟悉之後再到瘋狂程設考試(一定要懂如何查 JAVA API 與使用英漢字典) Java 考試常用的方法或類別 Eclipse 常用小技巧 CPE 一顆星選集： 編號 | 題目名稱 | 歷屆考古題日期 1. Vito's family (CPE10406, UVA10041) 2024/04/23 可與第 40 題一起看 2. Hashmat the brave warrior (CPE10407, UVA10055) 3. Primary Arithmetic (CPE10404, UVA10035) 　 2011/05/25、2023/03/21 4. The 3n + 1 problem (CPE10400, UVA100) 　 2010/06/09 5. You can say 11 (CPE10460, UVA10929) 　 2011/12/20 6. Bangla Numbers (CPE10414, UVA10101) 　 2018/12/18 7. List of Conquests (CPE21924, UVA10420) 　 2019/03/26 　　可與 第 8, 11, 43 題一起看 字元與字串 8. What's Cryptanalysis? (CPE10402, UVA10008) 　　可與 第 7, 11, 43 題一起看 9. Decode the Mad man (CPE10425, UVA10222) 　 2021/10/19 10. Problem J: Summing Digits (CPE10473, UVA11332) ...
Read more »

Visual Studio 自動排版格式化程式碼

圖片
在團隊開發過程中，什麼時候是程式碼瘋狂修改的階段呢， 無非就是Code Review了，有時候卡個幾天或是幾個月都是有可能的， 裡面常出現的comment，每次幾乎都會出現的就是排版的問題， 例如空白多一個少一個，括號還沒換行等等的小瑕疵， 對於心思不夠細膩的人而言，真的十分的惱人 團隊中喜歡將大括號換行， 例如： if(true) {   //code } else {   //code } 那也許有些團隊喜歡： if(true){   //code }else{   //code } 有時候不只括號要不要換行，連else要不要換行都有各自的喜好， 所以有時候要統一使用團隊規定的喜好真的會有眼殘的時候， 自己檢查老半天可能還是有漏網之魚， 但現在不用擔心啦！ 只要使用Format 格式化文件就能為你分憂解勞， 設定方式如下： 編輯 > 進階 > 格式化文件 Visual Studio會根據你的環境設定幫你自動重新排版 設定方式如下： 工具 > 選項 切換到 文字編輯器 > C# >程式碼樣式 > 格式化 > 新行 這邊可以設定很多換行的邏輯， 將對應的項目打勾跟取消勾選，下面的黑色區域會顯示排版的格式， 可根據自己或是團隊的喜好去做調整，即可自動排出你想要的格式囉！ 如果覺得 編輯 > 進階 > 格式化文件 這個選項太難找到， 可以參考這篇文章，將他加入在明顯的工具列區域喔 http://greens2314.blogspot.tw/2017/09/visual-studio-2015.html
Read more »

1. Vito's family (CPE10406, UVA10041) - CPE一顆星解答與說明

圖片
    👉   CPE 一顆星選集列表(49題) 題目說明與解答 題目 Vito 在紐約有非常多的親戚，他希望在紐約找到一間房子，這間房子到每個親戚家的距離總和，要是最少的距離 輸入說明 輸入資料包含很多筆測試資料 每筆測資，包含親戚數量與每位親戚家的街號 親戚數量介於1~499、街道範圍介於1~29999 多位親戚可住在同一條街 輸出說明 針對每筆測試資料，計算出 Vito 到每位親戚家的最短距離總和 街與街的距離 = 街道數字相減取絕對值 解題技巧 中位數 是指一組數字的中間數字；即是有一半數字的值大於中位數，而另一半數字的值小於中位數，其意義是在所有資料中居於中間位置的代表 排序 街道的數字同時代表距離，透過排序，可得知中位數 解題過程 取得輸入 取得資料筆數 根據資料筆數取得親戚數量 根據親戚數量取得街道編號 將街道編號存入陣列中 將親戚的街道位置 由小至大 排序 呼叫 Arrays 類別提供的 sort() 方法 https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html 假設親戚有 5 位，分別住在：2、5、8、4、2街 排序後為：2 、2、4、5、8街 計算中位數 中位數在陣列中的索引 = 親戚數量 / 2 假設親戚有 5 位( 奇數) ，分別住在：2、5、8、4、2街 排序後為：2 、2、4、5、8街，其中 4 為中位數，中位數有 1 個 5位親戚 / 2 = 2.5，取整數，陣列索引 2 的位置，儲存的是第 4 街 假設親戚有 4位 (偶數) ，分別住在：2、5、8、4街 排序後為：2 、4、5、8街，其中 4 或 5 為中位數， 中位數有 2 個，擇一即可 4位親戚 / 2 = 2，陣列索引 2 的位置，儲存的是 5 街 計算最小距離總和並印出 宣告 sum 變數，統計距離 使用 foreach 將各街道編號 減掉 中位數編號，取絕對值並進行家總 取絕對值要呼叫  Math.abs ()  方法 奇數情況 ： 中位數有 1 個 假設親戚有 5 位   ，分別住在： 2 、2、 4 、5、8 街 中位數 4 ，Vito 住在 4 街，到其他親戚家的距離總和即是最小值 9   偶數情況 ： ...
Read more »