小菜一碟

  前言 今天要來介紹 內插搜尋法 ，這個名字聽起來就很抽象，不容易知道這個演算法是如何進行搜尋的，一起來認識它吧！ 生活常識 唸大學的時候，如果可以 自由挑選座位 ，你都是做在哪邊的位置上呢？是挑前面的位置認真 上課 ，還是挑後面的位置方便 翹課 XD，想必你對於坐前面或坐後面有一套自己的挑選方式，而如果是站在 授課老師的角度 ，老師會 挑選 坐 前面 的學生來回答問題，還是挑 後面 的學生來回答問題呢？如何在教室內挑到一位合適的學生來回答不同難易程度的問題，這真的是很考驗老師的搜尋能力，感覺坐越 前面 的 參與度越高 ，越 後面 的 參與度越低 ，到底要挑選哪一區的哪一位同學來回答，想必老師也有一套挑選學生的方式 圖片來源: https://www.pexels.com/zh-tw/photo/207691/ 專業知識 - 內插搜尋法 Interpolation Search 內插搜尋法 又稱 插補搜尋法 ，主要是針對 已排序 的資料進行搜尋，算是二分搜尋法的改良版本，二分法會先找中間值，但 內插 搜尋法會透過 斜率公式 初步估算資料可能出現在 哪個的位置 ，很像在一個 範圍 內 插入 一個可能的位置，並逐漸 縮小 搜尋範圍 斜率公式 可參考維基百科 圖片來源: https://zh.wikipedia.org/wiki/%E6%96%9C%E7%8E%87 插補搜尋法公式 假設  X 軸 為陣列索引 ， Y 軸 為 由小到大 排列的儲存的數值，我們可藉由 終點(x2, y2)與起點(x1, y1)的斜率 會等於 目標點(x-key, y-value)與起點(x1, y1)的斜率`去推出資料可能的位置 例子 有一數列：1, 22, 32, 48, 56, 63, 47, 82, 94，共 9 個數值，由小到大排列，要找 48 在哪裡，套用公式時，若求出來的值有小數點則四捨五入(或使用你習慣的方式處理小數點也可以)，以下分為兩個步驟進行搜尋： 第一次的公式代入得到 X 軸 = 4 ，則去找陣列索引 4 的位置，找到的數值為 56 ，56 不等於 48，繼續搜尋 第二次的公式代入，得到數值 X 軸 = 3，則去找陣列索引 3 的位置，找到的數值為 48 ，48 等於 48，成功找到數值則結束搜尋 分析 效能的好壞取決於數值的分佈，如果資料分佈的越平...

  前言 今天要來介紹 循序搜尋法 與 二元搜尋法 ，這兩者有什麼差別呢？一起來看看吧 生活常識 你有去書局買過壁報紙嗎？如果朋友拿了一張藍色小紙片，請你到書局幫忙添購同顏色的紙張，而你第一次買也不清楚到底是要買深一點的藍色，還是淺一點的藍色，那麼書局的色卡可能是你的好幫手，因為 色卡 大多是按照顏色與深淺下去 排列 ，只要與你手上的顏色相比對就知道要買哪一種顏色，而你會怎麼比對呢？ 從頭到尾 逐一比對直到找到為止，還是從色卡的 中間 的顏色然後每次都跳好幾個格子開始比？ 圖片來源: 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) 二元搜尋法 又稱 二搜尋法 ，是針對已經 排序好 的資料進行搜尋，二元搜尋法會取出數列的 中間值 與 想要找的數值 進行 ...

  擁抱「資料結構」的「演算法」(24) - 搜尋 Search前言 搜尋演算法可以讓我們學習到很多搜尋技巧，可以快速協助我們找到想要的資料，一起來看看背後的搜尋原理吧 生活常識 你有玩過 嗒寶 Dobble Classic 嗎？這款桌遊就是在比賽誰找東西的速度最快，有興趣可以到博客來看一下介紹哦！我自己有入手一盒！非常好玩XD，而且他還有線上服務可以將內容置換成你自己想要的內容，非常的有趣 參考來源: 博客來 你有找東西的經驗嗎？找書、找衣服、找信件、找聯絡人，通常什麼是最難找的呢，如果沒有事先沒有透過好的分類、好的收納或好的管理，可能會在找東西時找的很辛苦XD 圖片來源: https://www.pexels.com/zh-tw/photo/4855329/ 另外申請一些網路服務的時候，像是會員申請或是會員登入時，系統可以快速辨別此用戶是否已經註冊過，或是登入時的帳號密碼是否輸入正確，想像看看在登入 Facebook 時，系統是如果在 30 億的用戶中，快速搜尋到我們的帳戶資料的呢 圖片來源: https://www.pexels.com/zh-tw/photo/facebook-facebook-fb-162622/ 專業知識 - 搜尋 Search 根據資料的儲存方式，還有搜尋演算法的選擇，會影響搜尋的時間，而搜尋演算法主要有四個分類 分類 內部搜尋(Internal Searching) 若資料量很小，則可將所有資料載入記憶體進行搜尋，就像是我們要找鉛筆盒裡面的筆，可以將筆通通掏出來放自己的桌上慢慢找 外部搜尋(External Searching) 若資料量大，就無法將資料載入到記憶體，記憶體會爆滿，這時候需要使用其他的輔助記憶體來協助，像是硬碟，就像是公司本部已經沒有足夠的空間存放資料，就只能在外面買新的地或租用外部倉庫 靜態搜尋(Static Searching) 在搜尋過程中，資料是 固定 的，可以預知資料的內容，並不會出現新增或刪除的現象，例如：我們要找某一篇報紙上的英文文章，其中英文字母 A 總共出現幾次，而這篇文章在印刷之後是不會改變的，我們不用擔心在搜尋過程中，會有搜尋錯誤的問題 動態搜尋(Dynamic Searching) 在搜尋過程中，資料是 不固定 的，可能會出現新增或刪除的變動，例如：在圖書館借書時，雖然在家有事先查過想借...

  前言 堆積 也是資料結構的其中一種，也是一個 完整的二元樹 ，而堆積的特色就是最大的數值會放在樹根，或是最小的數值會放在樹根，所以樹根會是最大值或最小值，接著我們就可以使用堆積排序法，將資料 由大至小 或 由小至大 排序完成 生活常識 喝飲料的時候常常可以觀察到，有些東西會沉在杯底，例如珍珠，有些東西則會浮在飲料上面，像是冰塊或水果切片，而根據物品的體積或密度，可以推得它們在水杯中的固定的常態 分佈 和固定的 順序 ，繼續丟入冰塊，冰塊只會浮在水面，不會沉下去 圖片來源: https://unsplash.com/photos/Q4Ha5yEzb9E 你有聽過 重要緊急四象限法則 嗎？通常在一天內，我們需要處理很多事情，除了吃喝拉撒睡，還要認真工作或認真念書，有時候忙起來真的會當機，不知道到底該處理哪一件事情才好，本來不急的事情因為規畫不當，變成非常緊急，或是非常緊急的事情或沒有趕緊處理而造成大麻煩的事件也層出不窮，可能就是 時間管理 上面需要做一些調整，而 重要緊急四象限法則 可以協助我們找出事情的 優先順序 ，讓我們清楚接下來要優先處理哪些事情 圖片來源: https://www.pexels.com/zh-tw/photo/3760810/ 資料結構的堆積會將資料按 優先順序 排列，讓我們可以清楚知道現在最急或最不緊急的事情有哪一些，讓我們一起來認識認識吧 專業知識 - 堆積 Heap 堆積 在之前的資料結構的部份並沒有介紹到，所以先來介紹一下什麼是堆積，有了基礎觀念之後再來認識堆積排序法，堆積是 完整的二元樹 ，數值的排列分為兩種： 最大堆積樹(Max-Heap) 與 最小堆積樹(Min-Heap) ，不論是哪一種，當堆疊中有數據被新增時，根據此數據的大小，會被調整到它應該出現的位置，這就是 堆積 的特性，就像上述水杯中的物品一樣，會根據某些條件，出現在它應該出現的位置 堆積樹種類 最大堆積樹(Max-Heap) 樹根為 最大值 ，所有節點的值都會 大於等於 子節點的值 最小堆積樹(Min-Heap) 樹根為 最小值 ，所有節點的值都會 小於等於 子節點的值 二元樹轉堆積樹 有一顆 二元樹   2, 8, 12, 4, 10, 14, 6 將 二元樹 轉成 最大堆積樹 ，子點節與樹根節點比較大小，較大者要與樹根節點交換位置 例如位置2的...

  前言 合併排序法 顧名思義就是會有合併的動作，在 合併 之前想必應該會有 切割 的動作，一起來看看這這 分分合合 的演算法吧XD 生活常識 你有用切水果的經驗嗎？通常我們都習慣將一顆水果 對半切 ，因為一整顆的水果比較不容易直皆整顆嗑，例如：西瓜XD，在對半切再對半切至 小塊 之後，就很容易不知不覺吃掉半顆，最後通通在肚子裡面 集合 了XD 圖片來源: https://www.pexels.com/zh-tw/photo/952480/ 對半的這個概念，也很像有些店家的手工麵的製作過程，會看到師傅把麵團甩成麵條，過程中不斷的對折再對折，最後在剪斷就會變成可以下鍋煮的麵了 圖片來源: https://www.pexels.com/zh-tw/photo/3771814/ 這樣一路分之後，會發生什麼事呢？就像三國演義裡面有這麼一句話：「天下大勢，分久必合，合久必分。」，其中的 分久必合 很有合併排序演算法的味道， 分裂 完之後，就會開始 統一 圖片來源: https://www.books.com.tw/products/0010854705?sloc=main 團康遊戲中的「我是拳王」，就是在活動一開始， 每一個人為一個單位 ，去找另一個人猜拳，如果猜輸，輸的人就要搭著猜贏者的肩膀成為他的隊友，如果猜贏，則可繼續找人猜拳，猜著猜著隊伍的人數會越來越多，最後剩下兩個隊伍時最刺激，因為猜贏者就是最大的勝利者，所有人都要排勝利者的後面，從此活動可以觀察出，從一開始一個人為單位，最後會 合併成一大群人 專業知識 - 合併排序法 Merge Sort 合併演算法會將資料對切為兩個部分，然後再將左半邊與右半邊繼續再切一半，切到最小單位，也就是只剩下一個數值，已無法再被切割為止，然後再進行小單位之間整合，再到大單位之間的整合，最後將全部資料都排序好 分割 取得資料長度，除以 2 之後， 將資料分為兩個區塊 例如：有一陣列資料為： 3, 8, 1, 7, 4, 2, 6, 5 ，共 8 個資料，除以 2 ，陣列會被分割為 2 個陣列  3, 8, 1, 7  與  4, 2, 6, 5 ，各自的長度為 4 重覆第 1 個步驟，再將資料，除以 2 之後， 將資料分為兩個區塊 例如： 3, 8, 1, 7 會被分割為 2 個陣列，長度為 2 ： ...