Java實現(xiàn)查找算法的示例代碼(二分查找、插值查找、斐波那契查找)
1.查找概述
查找表: 所有需要被查的數(shù)據(jù)所在的集合,我們給它一個統(tǒng)稱叫查找表。查找表(Search Table)是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。
查找(Searching): 根據(jù)給定的某個值,在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素(或記錄)。若表中存在這樣的一個記錄,則稱查找是成功的,此時查找的結(jié)果給出整個記錄的信息,或指示該記錄在查找表中的位置;若表中不存在關(guān)鍵字等于給定值的記錄,則稱查找不成功,此時查找的結(jié)果可給出一個“空”記錄或“空”指針。
查找表分類: 查找表按照操作方式來分有兩大種:靜態(tài)查找表和動態(tài)查找表。
靜態(tài)查找表(Static Search Table),只作查找操作的查找表。它的主要操作有:
- 查詢某個“特定的”數(shù)據(jù)元素是否在查找表中。
- 檢索某個“特定的”數(shù)據(jù)元素和各種屬性。
動態(tài)查找表(Dynamic Search Table),在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素,或者從查找表中刪除已經(jīng)存在的某個數(shù)據(jù)元素。顯然動態(tài)查找表的操作就是兩個:
- 查找時插入數(shù)據(jù)元素。
- 查找時刪除數(shù)據(jù)元素。
查找結(jié)構(gòu): 為了提高查找的效率,我們需要專門為查找操作設(shè)置數(shù)據(jù)結(jié)構(gòu),這種面向查找操作的數(shù)據(jù)結(jié)構(gòu)稱為查找結(jié)構(gòu)。
從邏輯上來說,查找所基于的數(shù)據(jù)結(jié)構(gòu)是集合,集合中的記錄之間沒有本質(zhì)關(guān)系??墒且氆@得較高的查找性能,我們就不能不改變數(shù)據(jù)元素之間的關(guān)系,在存儲時可以將查找集合組織成表、樹等結(jié)構(gòu)。
例如,對于靜態(tài)查找表來說,我們不妨應(yīng)用線性表結(jié)構(gòu)來組織數(shù)據(jù),這樣可以使用順序查找算法,如果再對主關(guān)鍵字排序,則可以應(yīng)用二分查找等技術(shù)進行高效的查找。
如果是需要動態(tài)查找,則會復(fù)雜一些,可以考慮二叉排序樹的查找技術(shù)。
另外,還可以用散列表結(jié)構(gòu)來解決一些查找問題。
2.順序查找
順序查找(Sequential Search)又叫線性查找,是最基本的查找技術(shù),它的查找過程是:從表中第一個(或最后一個)記錄開始,逐個進行記錄的關(guān)鍵字和給定值比較,若某個記錄的關(guān)鍵字和給定值相等,則查找成功,找到所查的記錄;如果直到最后一個(或第一個)記錄,其關(guān)鍵字和給定值比較都不等時,則表中沒有所查的記錄,查找不成功。
順序查找一般是一種在數(shù)組中查找數(shù)據(jù)的算法,是一種靜態(tài)查找。
順序查找的實現(xiàn): 順序查找非常簡單,就是從頭開始遍歷內(nèi)部數(shù)組,查看有沒有關(guān)鍵字(key)。有的話就返回對應(yīng)的索引。
設(shè)數(shù)組元素數(shù)量為n,則順序查找的查找成功最短時間為O(1),最長為O(n),查找失敗時間為O(n)。記作O(n)。
3.二分查找
3.1 二分查找概述
每次取中間記錄查找的方法叫做二分查找。二分查找也稱折半查找(Binary Search),它是一種效率較高的查找方法。但是,二分查找要求線性表必須采用順序存儲結(jié)構(gòu),而且表中元素按關(guān)鍵字有序排列。
二分查找的基本思想是:在有序表中,取中間記錄作為比較對象,若給定值與中間記錄的關(guān)鍵字相等,則查找成功;若給定值小于中間記錄的關(guān)鍵字,則在中間記錄的左半?yún)^(qū)繼續(xù)查找;若給定值大于中間記錄的關(guān)鍵字,則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程,直到查找成功,或所有查找區(qū)域無記錄,查找失敗為止。
設(shè)有序數(shù)組元素數(shù)量為n,將其長度減半log n 次后,其中便只剩一個數(shù)據(jù)了,這樣就能百分之百確定元素是否存在,則二分查找的查找成功最短時間為O(1),最長為O(logn)。查找失敗最短時間為時間為O(1),最長為O(logn)。記作O(logn)。
二分查找的時間復(fù)雜度為O(logn),與線性查找的O(n) 相比速度上得到了指數(shù)倍提高(x = log2n,則n = 2^x)。但是,二分查找必須建立在數(shù)據(jù)已經(jīng)排好序的基礎(chǔ)上才能使用,因此添加數(shù)據(jù)時必須加到合適的位置,這就需要額外耗費維護數(shù)組的時間。 而使用線性查找時,數(shù)組中的數(shù)據(jù)可以是無序的,因此添加數(shù)據(jù)時也無須顧慮位置,直接把它加在末尾即可,不需要耗費時間。
綜上,具體使用哪種查找方法,可以根據(jù)查找和添加兩個操作哪個更為頻繁來決定。
3.2 二分查找實現(xiàn)
對如下數(shù)據(jù){0,1,16,24,35,47,59,62,73,88,99}進行二分查找,是否存在73、72這兩個數(shù)。
public class Bisearch { /** * 有序的數(shù)組 */ public int[] elements = new int[]{1, 16, 24, 35, 47, 59, 62, 73, 88, 99}; @Test public void test1() { //7 System.out.println(bisearch(73)); //4 System.out.println(bisearch(47)); //-1 System.out.println(bisearch(72)); //求logn System.out.println(Math.log((double) 10) / Math.log((double) 2)); } /** * 折半查找的實現(xiàn) * * @param key 要查找的數(shù)據(jù) * @return 查找到的索引, 或者-1 表示查找到 */ public int bisearch(int key) { int low = 0; int high = elements.length - 1; int mid; //不在范圍內(nèi),直接返回-1 if (elements[low] > key || elements[high] < key) { return -1; } //開始折半查找 while (low <= high) { //折半 mid = (low + high) / 2; /*若查找值比中值小*/ if (elements[mid] > key) { //最高下標(biāo)調(diào)整到中位下標(biāo)小一位 high = mid - 1; /*若查找值比中值大*/ } else if (elements[mid] < key) { //最低下標(biāo)調(diào)整到中位下標(biāo)大一位 low = mid + 1; /*若查找值等于中值*/ } else { //說明mid即為查找到的位置 return mid; } } //未查找到,返回-1 return -1; } }
上面的數(shù)據(jù),采用二分查找之后其查找結(jié)構(gòu)如下圖:
從上圖可以看出來二分查找等于是把靜態(tài)有序查找表分成了兩棵子樹,即查找結(jié)果只需要找其中的一半數(shù)據(jù)記錄即可,等于工作量少了一半,然后繼續(xù)二分查找,循環(huán)重復(fù)執(zhí)行該操作就可以找到目標(biāo)數(shù)據(jù),或得出目標(biāo)數(shù)據(jù)不存在的結(jié)論,最高需要查找logn≈4次。效率當(dāng)然是非常高了。
4.插值查找
4.1 插值查找概述
插值查找(Interpolation Search),有序表的一種查找方式。 插值查找算法類似于二分查找,不同的是插值查找每次從自適應(yīng) mid 處開始查找。
這里的自適應(yīng),很好解釋,比如要在取值范圍0~10000之間100個元素從小到大均勻分布的數(shù)組中查找5,我們自然會考慮從數(shù)組下標(biāo)較小的開始查找。 將二分查找中的求 mid 索引的公式,變換一下格式得到:
也就是mid等于最低下標(biāo)low加上最高下標(biāo)high與low的差的一半。算法科學(xué)家們考慮的就是將這個1/2進行改進,改進為下面的計算方案:
假設(shè)a[10]={1,16,24,35,47,59,62,73,88,99},low=0,high=9,則a[low]=1,a[high]=99,如果我們要找的是key=16時,按原來折半的做法,我們需要四次才可以得到結(jié)果,但如果用新辦法,計算(key-a[low])/(a[high]-a[low])=(16-1)/(99-1)≈0.153,即mid≈0+0.153×(9-0)=1.377,取整得到mid=1,我們只需要一次就查找到結(jié)果了,顯然大大提高了查找的效率。
這就是插值查找和二分查找的不同之處,插值查找是根據(jù)要查找的關(guān)鍵字key與查找表中最大最小記錄的關(guān)鍵字比較后的查找方法,其核心就在于插值的計算公式(key-a[low])/(a[high]-a[low])。從時間復(fù)雜度來看,它也是O(logn),但對于表長較大,而關(guān)鍵字分布又比較均勻的查找表來說,插值查找算法的平均性能比折半查找要好得多。反之,由于插值的計算依賴于最大值和最小值,因此數(shù)組中如果分布類似{0,1,2,2000,2001,......,999998,999999}這種極端不均勻的數(shù)據(jù),用插值查找效率比二分查找低。因此插值查找應(yīng)用有限。
4.2 插值查找實現(xiàn)
public class FibonacciSearch { /** * 有序的數(shù)組 */ public int[] elements = new int[]{1, 16, 24, 35, 47, 59, 62, 73, 88, 99}; /** * 插值查找的實現(xiàn) * * @param key 要查找的數(shù)據(jù) * @return 查找到的索引, 或者-1 表示查找到 */ public int interpolationSearch(int key) { int low = 0; int high = elements.length - 1; int mid; //不在范圍內(nèi),直接返回-1 if (elements[low] > key || elements[high] < key) { return -1; } //開始插值查找 while (low <= high) { //插值 mid = low + (high - low) * (key - elements[low]) / (elements[high] - elements[low]); /*若查找值比中值小*/ if (elements[mid] > key) { //最高下標(biāo)調(diào)整到中位下標(biāo)小一位 high = mid - 1; /*若查找值比中值大*/ } else if (elements[mid] < key) { //最低下標(biāo)調(diào)整到中位下標(biāo)大一位 low = mid + 1; /*若查找值等于中值*/ } else { //說明mid即為查找到的位置 return mid; } } //未查找到,返回-1 return -1; } @Test public void test1() { System.out.println(interpolationSearch(315)); } }
5.斐波那契查找
5.1 斐波那契查找概述
斐波那契查找(Fibonacci Search)也是有序表的一種查找方式,同樣屬于二分查找的一個優(yōu)化,它是利用了黃金分割原理(斐波那契數(shù)列)來實現(xiàn)的。改變了中間結(jié)點(mid)的位置,mid不再是中間或插值得到,而是位于黃金分割點附近,即mid=low+F(k-1)-1(F代表斐波那契數(shù)列)。
斐波那契數(shù)列:即1,1,2,3,5,8,13...,從第三個數(shù)開始,后面的數(shù)都等于前兩個數(shù)之和,而斐波那契查找就是利用的斐波那契數(shù)列來實現(xiàn)查找的。初始化的斐波那契數(shù)列最后一位要大于等于數(shù)組元素的size-1。
查找步驟:
假設(shè)表中有 n 個元素,查找過程為獲取區(qū)間的下標(biāo) mid=low + fibonacci[k - 1] - 1 ,對 mid 的關(guān)鍵字與給定值的關(guān)鍵字比較:
- 如果與給定關(guān)鍵字相同,則查找成功,返回mid和high的最小值;
- 如果給定關(guān)鍵字大,向右查找并減小2個斐波那契區(qū)間;
- 如果給定關(guān)鍵字小,向左查找并減小1個斐波那契區(qū)間;
- 重復(fù)過程,直到找到關(guān)鍵字(成功)或區(qū)間為空集(失敗)。
5.2 斐波那契查找實現(xiàn)
public class FibonacciSearch { /** * 有序的數(shù)組 */ public int[] elements = new int[]{1, 16, 24, 35, 47, 59, 62, 73, 88, 99}; /** * 對應(yīng)的斐波拉契數(shù)組,數(shù)組的最大值>=elements.length-1 */ public int[] fibonacci = new int[]{1, 1, 2, 3, 5, 8, 13}; @Test public void test1() { //3 System.out.println(fibonacciSearch2(35)); } /** * 斐波那契查找的實現(xiàn) * * @param key 要查找的數(shù)據(jù) * @return 查找到的索引, 或者-1 表示查找到 */ public int fibonacciSearch2(int key) { //最小索引 int low = 0; //最大索引 int high = elements.length - 1; //不在范圍內(nèi),直接返回-1 if (elements[low] > key || elements[high] < key) { return -1; } int k = 0, i, mid; /*計算high位于斐波那契數(shù)列的位置 */ //這里high為9,fibonacci[5]<9<fibonacci[6] ,取大的,即k=6 while (high > fibonacci[k]) { k++; } /*擴展數(shù)組*/ //擴展原數(shù)組,長度擴展為fibonacci[k]=13,即多加了三個位置elements[10],elements[11],elements[12] elements = Arrays.copyOf(elements, fibonacci[k]); //為了保證數(shù)組的順序,把擴展的值都設(shè)置為原始數(shù)組的最大值 for (i = high + 1; i < elements.length; i++) { elements[i] = elements[high]; } /*開始斐波那契查找*/ while (low <= high) { /* 計算當(dāng)前分隔的下標(biāo)索引,取的是黃金分割點 7-4-2-1-0 7-10*/ mid = low + fibonacci[k - 1] - 1; /* 若查找記錄小于當(dāng)前分隔記錄 */ if (key < elements[mid]) { /* 最高下標(biāo)調(diào)整到分隔下標(biāo)mid-1處 */ high = mid - 1; /* 斐波那契數(shù)列下標(biāo)減一位 */ k = k - 1; } /* 若查找記錄大于當(dāng)前分隔記錄 */ else if (key > elements[mid]) { /* 最低下標(biāo)調(diào)整到分隔下標(biāo)mid+1處 */ low = mid + 1; /* 斐波那契數(shù)列下標(biāo)減兩位 */ k = k - 2; } else { /* 若mid <= high則說明mid即為查找到的位置,返回mid */ /* 若mid>high說明是補全數(shù)值,返回high */ return Math.min(mid, high); } } return -1; } }
具體步驟
如果查找的key等于35:
- 程序開始運行,數(shù)組elements={1,16,24,35,47,59,62,73,88,99},high =9,要查找的關(guān)鍵字key=35。注意此時我們已經(jīng)有了事先計算好的全局變量數(shù)組fibonacci的具體數(shù)據(jù),它是斐波那契數(shù)列,fibonacci ={1,1,2,3,5,8,13},計算原則是斐波那契數(shù)列的最大值是大于等于elements.length-1的最小值。
- 計算high=9位于斐波那契數(shù)列的索引位置,可能是位于某兩個索引位置之間,那么取最大的索引位置。fibonacci[5]<9<fibonacci[6] ,取大的,即k=6。
- fibonacci[6]=13,計算時數(shù)組長度應(yīng)該為13,因此我們需要對原數(shù)組elements擴展長度10至13,擴展后后面的索引位置均沒有賦值,為了保證數(shù)組的有序,賦值為原素組elements的最大值elements[10]= elements[11]= elements[12]= elements[9]。
- 然后開始斐波那契查找:
尋找mid下標(biāo),由于low=0且k=6,我們第一個要對比的數(shù)值是從下標(biāo)為mid=0 + fibonacci[6 - 1] – 1 = 7開始的。
此時elements[7]=73>key=35,因此查找記錄小于當(dāng)前分隔記錄;得到high=7-1=6,k=6-1=5。再次循環(huán),計算mid=0+F[5-1]-1=4。
此時elements[4]=47>key=35,因此查找記錄小于當(dāng)前分隔記錄;得到high=4-1=3,k=5-1=4。再次循環(huán),mid=0+F[4-1]-1=2。
此時elements[2]=24<key=35,因此查找記錄大于當(dāng)前分隔記錄;得到low=2+1=3,k=4-2=2。再次循環(huán),mid=3+F[2-1]-1=3。
此時elements[3]=35<key=35,因此查找記錄等于當(dāng)前分隔記錄;返回此時mid=3和high=3的最小值,斐波那契查找結(jié)束。即返回3
如果查找的key等于99:
前幾步都是一樣的,主要是斐波那契查找不一樣:
尋找mid下標(biāo),由于low=0且k=6,我們第一個要對比的數(shù)值是從下標(biāo)為mid=0 + fibonacci[6 - 1] – 1 = 7開始的。
此時elements[7]=73<key=99,因此查找記錄大于當(dāng)前分隔記錄;得到low=7+1=8,k=6-2=4。再次循環(huán),計算mid=8+F[4-1]-1=10。注意此時10的索引位置已經(jīng)到了擴展的三個元素中了。
此時elements[10]=99=key=99,因此查找記錄等于當(dāng)前分隔記錄;返回此時mid=10和high=9的最小值,斐波那契查找結(jié)束,即返回9。
這里可以看出來擴展數(shù)組的用意,因為mid有可能算出超出原數(shù)組索引長度的索引;同時也可以看出來最后還要比較取最小值的用意,因為擴展的元素只是我們比較時添加的,實際上原數(shù)組并不存在這個索引,因此要取high,即原數(shù)組存在的索引;同時這也是為擴展的元素賦值的用意,要保證mid有值-但是不超過最大值,因此就取最大值。
5.3 總結(jié)
如上圖,斐波那契查找的特點就是左側(cè)半?yún)^(qū)范圍大于右側(cè)半?yún)^(qū)范圍。如果要查找的記錄在mid右側(cè),則左側(cè)的數(shù)據(jù)都不用再判斷了,不斷反復(fù)進行下去,對處于右側(cè)當(dāng)中的大部分?jǐn)?shù)據(jù),其工作效率要高一些。 所以盡管斐波那契查找的時間復(fù)雜也為O(logn),但就平均性能來說,斐波那契查找要優(yōu)于二分查找??上绻亲顗那闆r,比如這里key=1,那么始終都處于左側(cè)長半?yún)^(qū)在查找,則查找效率要低于二分查找。
還有比較關(guān)鍵的一點,二分查找是進行加法與除法運算(mid=(low+high)/2),插值查找進行復(fù)雜的四則運算(mid=low+(highlow)*(key-a[low])/(a[high]-a[low])),而斐波那契查找只是最簡單加減法運算(mid=low+F[k-1]-1),在海量數(shù)據(jù)的查找過程中,這種細(xì)微的差別可能會影響最終的查找效率,但是斐波那契額查找同樣需要額外的空間。
以上就是Java實現(xiàn)查找算法的示例代碼(二分查找、插值查找、斐波那契查找)的詳細(xì)內(nèi)容,更多關(guān)于Java查找算法的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
SpringCloud與Consul集成實現(xiàn)負(fù)載均衡功能
負(fù)載均衡基本概念有:實服務(wù)、實服務(wù)組、虛服務(wù)、調(diào)度算法、持續(xù)性等,其常用應(yīng)用場景主要是服務(wù)器負(fù)載均衡,鏈路負(fù)載均衡。這篇文章主要介紹了SpringCloud與Consul集成實現(xiàn)負(fù)載均衡 ,需要的朋友可以參考下2018-09-09淺談Ribbon、Feign和OpenFeign的區(qū)別
這篇文章主要介紹了淺談Ribbon、Feign和OpenFeign的區(qū)別。具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-06-06淺談Spring AOP中args()和argNames的含義
這篇文章主要介紹了Spring AOP中args()和argNames的含義,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-07-07Java使用POI實現(xiàn)導(dǎo)出Excel的方法詳解
在項目開發(fā)中往往需要使用到Excel的導(dǎo)入和導(dǎo)出,導(dǎo)入就是從Excel中導(dǎo)入到DB中,而導(dǎo)出就是從DB中查詢數(shù)據(jù)然后使用POI寫到Excel上。本文將利用POI實現(xiàn)導(dǎo)出Excel,需要的可以參考一下2022-10-10IntelliJ IDEA 2021 Tomcat 8啟動亂碼問題的解決步驟
很多朋友遇到過IntelliJ IDEA 2021 Tomcat 8啟動的時候出現(xiàn)各種奇葩問題,最近有童鞋反映IntelliJ IDEA 2021 Tomcat 8啟動亂碼,正好我也遇到這個問題,下面我把解決方法分享給大家需要的朋友參考下吧2021-06-06spring?boot項目中集成rocketmq詳細(xì)步驟
這篇文章主要給大家介紹了關(guān)于spring?boot項目中集成rocketmq的相關(guān)資料,springboot集成rocketmq的方法非常簡單,文中直接上代碼,需要的朋友可以參考下2023-09-09