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