今天這篇博客就聊聊幾種常見的查找算法，當(dāng)然本篇博客只是涉及了部分查找算法，接下來的幾篇博客中都將會介紹關(guān)于查找的相關(guān)內(nèi)容。本篇博客主要介紹查找表的順序查找、折半查找、插值查找以及Fibonacci查找。本篇博客會給出相應(yīng)查找算法的示意圖以及相關(guān)代碼，并且給出相應(yīng)的測試用例。當(dāng)然本篇博客依然會使用面向?qū)ο笳Z言Swift來實(shí)現(xiàn)相應(yīng)的Demo，并且會在github上進(jìn)行相關(guān)Demo的分享。
查找在生活中是比較常見的，本篇博客所涉及的這幾種查找都是基于線性結(jié)構(gòu)的查找。也就是說我們的查找表是一個線性表，我們要查找某個元素在線性表中的位置。順序查找就是從頭到尾一個個進(jìn)行比較，直到找到為止，此方法適用于無序的查找表。而折半查找、插值查找以及Fibonacci查找的查找表都是有序的，下方的內(nèi)容會詳細(xì)的介紹到。進(jìn)入今天博客的主題。
一、查找協(xié)議的定義
因?yàn)楸酒┛臀覀兩婕安檎冶淼亩喾N查找方式，而且查找表的數(shù)據(jù)結(jié)構(gòu)都是線性結(jié)構(gòu)?；?span style="color:#FF0000;">Swift面向?qū)ο笳Z言的特征以及面向接口編程的原則，我們先給我們所有的查找方式定義一個協(xié)議。本篇博客中所有的查找方式都會遵循這個查找類型，這樣便于外部統(tǒng)一調(diào)用，也方便我們測試和擴(kuò)展。
下方這個SearchType協(xié)議就是我們所定義的查找協(xié)議。下方這個協(xié)議雖然比較簡單，但是還是比較重要的，協(xié)議中定義了本篇博客所涉及的查找方式對外的調(diào)用方式。協(xié)議中的search()方法就是外部要調(diào)用的方法。該函數(shù)第一個參數(shù)就是要查找的查找表，第二個參數(shù)就是要查找的關(guān)鍵字。該函數(shù)的返回值就是關(guān)鍵字在查找表中的位置。如果沒有找到就會返回0。
二、順序查找
上面也簡單的提了一下，順序查找表是從頭到尾以此進(jìn)行對比，直到找到我們要查找的元素位置。如果未找到，就返回
