欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實現(xiàn)查找算法的示例代碼(二分查找、插值查找、斐波那契查找)

 更新時間:2022年01月19日 14:47:21   作者:劉Java  
查找就是根據(jù)給定的某個值,在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。本文介紹了常見的數(shù)據(jù)查找算法:順序查找、二分查找、插值查找和斐波那契查找等以及相應(yīng)的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),只作查找操作的查找表。它的主要操作有:

  1. 查詢某個“特定的”數(shù)據(jù)元素是否在查找表中。
  2. 檢索某個“特定的”數(shù)據(jù)元素和各種屬性。

動態(tài)查找表(Dynamic Search Table),在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素,或者從查找表中刪除已經(jīng)存在的某個數(shù)據(jù)元素。顯然動態(tài)查找表的操作就是兩個:

  1. 查找時插入數(shù)據(jù)元素。
  2. 查找時刪除數(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ù)載均衡功能

    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ū)別

    這篇文章主要介紹了淺談Ribbon、Feign和OpenFeign的區(qū)別。具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • Spring中的異步方法@Async失效的原因詳解

    Spring中的異步方法@Async失效的原因詳解

    這篇文章主要介紹了Spring中的異步方法@Async失效的原因詳解,@Async屬于異步注解,@Async放在方法上標(biāo)識該方法為異步方法,異步是指進程不需要一直等待下去,而是繼續(xù)執(zhí)行下面的操作,不管其他進程的狀態(tài),需要的朋友可以參考下
    2024-01-01
  • Java獲取文件ContentType案例

    Java獲取文件ContentType案例

    這篇文章主要介紹了Java獲取文件ContentType案例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-08-08
  • Spring中的聲明式事務(wù)控制詳解

    Spring中的聲明式事務(wù)控制詳解

    這篇文章主要介紹了Spring中的聲明式事務(wù)控制詳解,Spring的聲明式事務(wù)顧名思義就是采用聲明的方式來處理事務(wù),這里所說的聲明,就是指在配置文件中聲明,用在Spring配置文件中聲明式的事務(wù)處理來代替代碼是的處理事務(wù),需要的朋友可以參考下
    2024-01-01
  • 淺談JAVA并發(fā)之ReentrantLock

    淺談JAVA并發(fā)之ReentrantLock

    本文主要介紹了基于AQS實現(xiàn)的ReentrantLock(重入鎖),感興趣的同學(xué),可以參考下。
    2021-06-06
  • 淺談Spring AOP中args()和argNames的含義

    淺談Spring AOP中args()和argNames的含義

    這篇文章主要介紹了Spring AOP中args()和argNames的含義,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-07-07
  • Java使用POI實現(xiàn)導(dǎo)出Excel的方法詳解

    Java使用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-10
  • IntelliJ IDEA 2021 Tomcat 8啟動亂碼問題的解決步驟

    IntelliJ IDEA 2021 Tomcat 8啟動亂碼問題的解決步驟

    很多朋友遇到過IntelliJ IDEA 2021 Tomcat 8啟動的時候出現(xiàn)各種奇葩問題,最近有童鞋反映IntelliJ IDEA 2021 Tomcat 8啟動亂碼,正好我也遇到這個問題,下面我把解決方法分享給大家需要的朋友參考下吧
    2021-06-06
  • spring?boot項目中集成rocketmq詳細(xì)步驟

    spring?boot項目中集成rocketmq詳細(xì)步驟

    這篇文章主要給大家介紹了關(guān)于spring?boot項目中集成rocketmq的相關(guān)資料,springboot集成rocketmq的方法非常簡單,文中直接上代碼,需要的朋友可以參考下
    2023-09-09

最新評論