擁抱「資料結構」的「演算法」(24) - 搜尋 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)
在搜尋過程中,資料是不固定
的,可能會出現新增或刪除的變動,例如:在圖書館借書時,雖然在家有事先查過想借的書還在圖書館內,但再前往圖書館或在找書的過程中,很有可能隨時會被其他人借走
搜尋演算法
搜尋演算法有非常多種,根據資料儲存方式的不同,搭配使用的演算法也不一樣,常見的有以下這幾種:
- 循序搜尋法(Sequential Search) / 線性搜尋法(Linear Search)
- 二元搜尋法(Binary Search) / 二分搜尋(Half-Interval Search)
- 內插搜尋法(Interpolation Search) / 插補搜尋法
- 費式搜尋法(Fibonacci Search) / 費伯那搜尋法
今日小結
明後兩天會逐一介紹這幾種常見的搜尋演算法
今日謎題
最近有一個畫展,裡面有一幅圖非常有名,聽說是OOOSa
,而進入畫展需要5位的數字密碼,請問你能從化學元素表中猜到密碼嗎?(讓大家體會一下搜尋的感覺XD)
圖片來源: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(堆疊)
留言
張貼留言