iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 24
1
Software Development

擁抱「資料結構」的「演算法」系列 第 24

擁抱「資料結構」的「演算法」(24) - 搜尋 Search

  • 分享至 

  • xImage
  •  

前言

搜尋演算法可以讓我們學習到很多搜尋技巧,可以快速協助我們找到想要的資料,一起來看看背後的搜尋原理吧


生活常識

你有玩過嗒寶 Dobble Classic嗎?這款桌遊就是在比賽誰找東西的速度最快,有興趣可以到博客來看一下介紹哦!我自己有入手一盒!非常好玩XD,而且他還有線上服務可以將內容置換成你自己想要的內容,非常的有趣
https://ithelp.ithome.com.tw/upload/images/20201008/2012984138W9QDVHzr.png
參考來源:博客來

你有找東西的經驗嗎?找書、找衣服、找信件、找聯絡人,通常什麼是最難找的呢,如果沒有事先沒有透過好的分類、好的收納或好的管理,可能會在找東西時找的很辛苦XD
https://ithelp.ithome.com.tw/upload/images/20201008/201298416w7hzfQWF4.png
圖片來源:https://www.pexels.com/zh-tw/photo/4855329/

另外申請一些網路服務的時候,像是會員申請或是會員登入時,系統可以快速辨別此用戶是否已經註冊過,或是登入時的帳號密碼是否輸入正確,想像看看在登入 Facebook 時,系統是如果在 30 億的用戶中,快速搜尋到我們的帳戶資料的呢
https://ithelp.ithome.com.tw/upload/images/20201008/20129841JqNVvwG9dC.png
圖片來源:https://www.pexels.com/zh-tw/photo/facebook-facebook-fb-162622/


專業知識 - 搜尋 Search

根據資料的儲存方式,還有搜尋演算法的選擇,會影響搜尋的時間,而搜尋演算法主要有四個分類

分類

  1. 內部搜尋(Internal Searching)
    若資料量很小,則可將所有資料載入記憶體進行搜尋,就像是我們要找鉛筆盒裡面的筆,可以將筆通通掏出來放自己的桌上慢慢找

  2. 外部搜尋(External Searching)
    若資料量大,就無法將資料載入到記憶體,記憶體會爆滿,這時候需要使用其他的輔助記憶體來協助,像是硬碟,就像是公司本部已經沒有足夠的空間存放資料,就只能在外面買新的地或租用外部倉庫

  3. 靜態搜尋(Static Searching)
    在搜尋過程中,資料是固定的,可以預知資料的內容,並不會出現新增或刪除的現象,例如:我們要找某一篇報紙上的英文文章,其中英文字母 A 總共出現幾次,而這篇文章在印刷之後是不會改變的,我們不用擔心在搜尋過程中,會有搜尋錯誤的問題

  4. 動態搜尋(Dynamic Searching)
    在搜尋過程中,資料是不固定的,可能會出現新增或刪除的變動,例如:在圖書館借書時,雖然在家有事先查過想借的書還在圖書館內,但再前往圖書館或在找書的過程中,很有可能隨時會被其他人借走

搜尋演算法

搜尋演算法有非常多種,根據資料儲存方式的不同,搭配使用的演算法也不一樣,常見的有以下這幾種:

  • 循序搜尋法(Sequential Search) / 線性搜尋法(Linear Search)
  • 二元搜尋法(Binary Search) / 二分搜尋(Half-Interval Search)
  • 內插搜尋法(Interpolation Search) / 插補搜尋法
  • 費式搜尋法(Fibonacci Search) / 費伯那搜尋法

今日小結

明後兩天會逐一介紹這幾種常見的搜尋演算法


今日謎題

最近有一個畫展,裡面有一幅圖非常有名,聽說是OOOSa,而進入畫展需要5位的數字密碼,請問你能從化學元素表中猜到密碼嗎?(讓大家體會一下搜尋的感覺XD)

https://ithelp.ithome.com.tw/upload/images/20201008/20129841QREQiK3233.png

https://ithelp.ithome.com.tw/upload/images/20201008/20129841y8otOH9NC1.png

圖片來源:https://www.pexels.com/zh-tw/photo/4001822/
https://zh.wikipedia.org/wiki/%E5%85%83%E7%B4%A0%E5%91%A8%E6%9C%9F%E8%A1%A8

昨日謎題

謎題說明:根據堆疊的特性,資料會以某種形式排列儲存,┼如果仔細觀察,先找出每個單字的字首,會得到 H、E、A、P,再將它們組成起來,答案就是 HEAP(堆疊)


上一篇
擁抱「資料結構」的「演算法」(23) - 堆積排序法
下一篇
擁抱「資料結構」的「演算法」(25) - 循序搜尋法與二元搜尋法
系列文
擁抱「資料結構」的「演算法」30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
neroal
iT邦新手 5 級 ‧ 2024-05-16 10:01:29

25113!
Mn:25
Na:11
Li:3

我要留言

立即登入留言