查找表

同一類型的數(shù)據(jù)元素（或記錄）的集合。

關(guān)鍵字

數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。若此關(guān)鍵字可以唯一地標(biāo)識(shí)一個(gè)記錄，則稱此關(guān)鍵字為主關(guān)鍵字（Primary key）。用以識(shí)別若干記錄的關(guān)鍵字，是次關(guān)鍵字（Secondary Key）。

查找

查找（Searching）是根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）。
若查找到了數(shù)據(jù)元素，則查找成功；否則，查找失敗。

查找分類：
1、靜態(tài)查找和動(dòng)態(tài)查找
靜態(tài)查找：特定元素是否存在；查找特定元素的屬性。
動(dòng)態(tài)查找：插入數(shù)據(jù)元素；刪除數(shù)據(jù)元素。

2、有序查找和無(wú)序查找

靜態(tài)查找表各種表示方法：以順序表或線性鏈表表示靜態(tài)查找表

順序表的順序查找例子：

    private static int arrays [] = {12,15,3,56,234,13,76,45,23};

    public static void main(String[] args) {
        System.out.println(findInt(45));
    }

    private static int findInt(int key){
        for(int i = 1; i <= arrays.length ; i++){
            if(arrays[i] == key){
                return arrays[i] ;
            }
        }
        return 0;
    }

那么簡(jiǎn)單的數(shù)據(jù)查找可以這樣做，如果是非常龐大的數(shù)據(jù)需要查找某個(gè)關(guān)鍵字的話，又怎么做呢？有沒(méi)有一個(gè)標(biāo)準(zhǔn)去衡量查找的優(yōu)劣呢？

我們需要知道如下幾個(gè)定義：
1、查找操作的性能分析：時(shí)間復(fù)雜度、空間復(fù)雜度、算法的其他性能。
2、衡量查找算法好壞的依據(jù)：其關(guān)鍵字和給定值進(jìn)行過(guò)比較的記錄個(gè)數(shù)的平均值”
3、平均查找長(zhǎng)度：為確定記錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值。

有序表的查找

折半查找、斐波那契查找、插值查找。

折半查找

    //折半查找算法
    public static int Binary_Search(int arr[], int n, int key) {
        int mid;
        int low = 1;//最低元素索引
        int high = n;//最高元素索引
        int flag = 0;//哨兵用來(lái)記錄查找次數(shù)
        while (low <= high) {
            mid = (low + high) / 2;
            if (key < arr[mid]) {
                high = mid - 1;
                flag++;
            } else if (key > arr[mid]) {
                low = mid + 1;
                flag++;
            } else
                return mid;
        }
        return 0;
    }

折半查找性能分析
折半查找查找過(guò)程也可用二叉樹(shù)描述

折半查找的效率比順序查找高，但折半查找只能適用于有序表，且限于順序存儲(chǔ)結(jié)構(gòu)（對(duì)線性鏈表無(wú)法進(jìn)行折半查找）。

插值查找：在折半查找的基礎(chǔ)上改進(jìn)。
在取值范圍1 ~ 10000 之間 100 個(gè)元素從小到大均勻分布的數(shù)組中查找5， 我們自然會(huì)考慮從數(shù)組下標(biāo)較小的開(kāi)始查找。那么就不一定是折半了，有可能折一小部分，有可能折更多。

   public static int chazhiSearch(int arr[], int n, int key) {
        int low, high, mid;
        low = 1;//最低元素索引
        high = n;//最高元素索引
        while (low <= high) {
            //關(guān)鍵算法，效率提高不少
            mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]);
            if (key < arr[mid]) {
                high = mid - 1;
            } else if (key > arr[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return 0;
    }

可見(jiàn)，關(guān)鍵字分布比較均勻的情況下，比折半查找更快，

斐波那契查找：
斐波那契查找的平均性能比折半查找的好，但最壞的情況比它差。還有一個(gè)優(yōu)點(diǎn)，分割時(shí)，只需進(jìn)行加、減運(yùn)算。

    public static int fibonacciSearch(int arr[], int n, int key) {
        //構(gòu)造一個(gè)斐波拉切數(shù)列
        int F[] = new int[20];
        F[0] = 0;
        F[1] = 1;
        for (int j = 2; j < F.length; j++) {
            F[j] = F[j - 1] + F[j - 2];//遞歸構(gòu)造斐波拉契數(shù)列
        }

        int mid;
        int i;
        int low = 1;
        int high = n;
        int k = 0;
        while (n > F[k] - 1) {
            k++;
        }
        for (i = n; i < F[k] - 1; i++) {
            arr[i] = arr[n];//必須擴(kuò)展對(duì)象數(shù)組的后面幾位元素，否則容易越界
        }
        while (low <= high) {
            mid = low + F[k - 1] - 1;
            if (key < arr[mid]) {
                high = mid - 1;
                k = k - 1;
            } else if (key > arr[mid]) {
                low = mid + 1;
                k = k - 2;
            } else {
                if (mid <= n) {
                    return mid;
                } else {
                    return n;
                }
            }
        }
        return 0;
    }

訪問(wèn)頻度域？
以上的查找都是等概率的查找，那不同概率的查找是怎么樣的呢？ 這就要用到 靜態(tài)樹(shù)表的查找
帶權(quán)路徑長(zhǎng)度和最短的為靜態(tài)最優(yōu)查找樹(shù)。
索引順序表的查找（分塊查找）
哈希查找?