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），只作查找操作的查找表。它的主要操作有：

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

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

1. 查找時(shí)插入數(shù)據(jù)元素。
2. 查找時(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)文章！

最新評(píng)論