今天這篇博客就聊聊幾種常見的查找算法，當然本篇博客只是涉及了部分查找算法，接下來的幾篇博客中都將會介紹關(guān)于查找的相關(guān)內(nèi)容。本篇博客主要介紹查找表的順序查找、折半查找、插值查找以及Fibonacci查找。本篇博客會給出相應查找算法的示意圖以及相關(guān)代碼，并且給出相應的測試用例。當然本篇博客依然會使用面向?qū)ο笳Z言Swift來實現(xiàn)相應的Demo，并且會在github上進行相關(guān)Demo的分享。

查找在生活中是比較常見的，本篇博客所涉及的這幾種查找都是基于線性結(jié)構(gòu)的查找。也就是說我們的查找表是一個線性表，我們要查找某個元素在線性表中的位置。順序查找就是從頭到尾一個個進行比較，直到找到為止，此方法適用于無序的查找表。而折半查找、插值查找以及Fibonacci查找的查找表都是有序的，下方的內(nèi)容會詳細的介紹到。進入今天博客的主題。

 

一、查找協(xié)議的定義

因為本篇博客我們涉及查找表的多種查找方式，而且查找表的數(shù)據(jù)結(jié)構(gòu)都是線性結(jié)構(gòu)?；?span style="color:#FF0000;">Swift面向?qū)ο笳Z言的特征以及面向接口編程的原則，我們先給我們所有的查找方式定義一個協(xié)議。本篇博客中所有的查找方式都會遵循這個查找類型，這樣便于外部統(tǒng)一調(diào)用，也方便我們測試和擴展。

下方這個SearchType協(xié)議就是我們所定義的查找協(xié)議。下方這個協(xié)議雖然比較簡單，但是還是比較重要的，協(xié)議中定義了本篇博客所涉及的查找方式對外的調(diào)用方式。協(xié)議中的search()方法就是外部要調(diào)用的方法。該函數(shù)第一個參數(shù)就是要查找的查找表，第二個參數(shù)就是要查找的關(guān)鍵字。該函數(shù)的返回值就是關(guān)鍵字在查找表中的位置。如果沒有找到就會返回0。

 

二、順序查找

上面也簡單的提了一下，順序查找表是從頭到尾以此進行對比，直到找到我們要查找的元素位置。如果未找到，就返回