一绰筛、查找表
1、定義
A.查找表（table）：由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合，由于“集合”中的數(shù)據(jù)元素間存在完全松散的關(guān)系爹袁，因此查找表是非常靈便的數(shù)據(jù)結(jié)構(gòu)，他是在實(shí)際應(yīng)用中被大量使用的數(shù)據(jù)結(jié)構(gòu)矮固。
B.關(guān)鍵字（key）：元素中某個(gè)數(shù)據(jù)項(xiàng)的值失息，用于標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，若關(guān)鍵字可唯一的標(biāo)識(shí)一個(gè)記錄档址，則為“主關(guān)鍵字（primary key）”盹兢，若能標(biāo)識(shí)若干記錄，則為“次關(guān)鍵字（secondary key）”
C.查找：根據(jù)給定值守伸，在查找表中確定一個(gè)其關(guān)鍵字 = 給定值的元素绎秒，如存在這一的記錄，則查找是成功的

2尼摹、查找表的操作
A.靜態(tài)查找表：查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中替裆，檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性
B.動(dòng)態(tài)查找表：在查找中同時(shí)插入查找表中不存在的元素校辩，從查找表中刪除一存在的元素

二、靜態(tài)查找表
1辆童、順序表的查找
從表中第n個(gè)記錄開始宜咒，逐個(gè)進(jìn)行關(guān)鍵字和給定值的比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等把鉴，則查找成功故黑。查找之前需要設(shè)置對(duì)r[0]的關(guān)鍵字賦值K，免去查找過程中每一步都要檢測(cè)整個(gè)表是否查找完畢庭砍，起到了監(jiān)視哨的作用场晶，當(dāng)然監(jiān)視哨也可以設(shè)在高下標(biāo)出。
順序查找的缺點(diǎn)：平均查找長(zhǎng)度較大怠缸，尤其當(dāng)n特別大時(shí)诗轻，查找效率低。
順序查找的優(yōu)點(diǎn)：算法簡(jiǎn)單揭北，適用面廣扳炬，對(duì)表的結(jié)構(gòu)物要求。

/* a為數(shù)組搔体，n為要查找的數(shù)組長(zhǎng)度恨樟，key為要查找的關(guān)鍵字 */
int Sequential_Search(int *a, int n, int key){
    for (int i = 0; i < n; i++){
        if (a[i] == key)
            return i;
    }
    return 0;
}

//順序查找優(yōu)化(有哨兵的順序查找)
int Sequential_Search2(int *a, int n, int key){
    int i;
    /* 設(shè)置a[0]為關(guān)鍵字值，我們稱之為“哨兵” */
    a[0] = key; 
    /* 循環(huán)從數(shù)組尾部開始 */
    i = n;     
    while (a[i] != key){
        i--;
    }
    /* 返回0則說明查找失敗 */
    return i;   
}

有哨兵的順序查找比普通查找少了一個(gè)比較（for循環(huán)中的i < n）疚俱，因此在大量數(shù)據(jù)的情況下劝术，有哨兵的順序查找比普通順序查找要快。
2呆奕、有序表的查找
A.折半查找：先確定待查記錄所在范圍（區(qū)間）养晋，然后逐步縮小范圍，直到找到或找不到記錄為止梁钾。
舉例：05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92有序表中中查找21和85
設(shè)指針low绳泉，hig為待查元素所在范圍的下界和上界，指針mid為指示區(qū)間的中間位置陈轿，即mid = [(low + hig) / 2]圈纺，此處秦忿，low何hig的初值為1和11麦射，即[1, 11]為待查范圍。
先查找K=21：

image.png

首先r[mid].key與K比較灯谣，由于r[mid].key > K潜秋，說明若待查元素存在，必在區(qū)間[low胎许， mid - 1]范圍內(nèi)峻呛，則指針hig指向第mid - 1個(gè)元素罗售，重新求得mid = [(1 + 5) / 2] = 3

image.png

image.png

image.png

static int BinarySearch(int [] a, int n, int key) {
    int low, high, mid;
    low = 0;
    high = n;
    while(low <= high){
        mid = (low + high) / 2; /* 折半  */
        if (key < a[mid]) {
            high = mid - 1;
        }
        else if (key > a[mid]) {
            low = mid + 1;
        }
        else
            return mid;
    }
    return 0;
}

折半查找的效率比順序查找高操禀，但只適用于有序表，且為順序存儲(chǔ)結(jié)構(gòu)横腿，對(duì)線性鏈表無法進(jìn)行折半查找颓屑。

B.斐波那契查找：根據(jù)斐波那契序列的特點(diǎn)對(duì)表進(jìn)行分割
舉例：有9個(gè)元素的數(shù)組array對(duì)應(yīng)的斐波那契數(shù)列（長(zhǎng)度先隨便取，只要最大數(shù)大于9即可）{1, 1, 2, 3, 5, 8, 13, 21, 34}蔑水，發(fā)現(xiàn)大于9且最接近9的斐波那契數(shù)值是F[6] = 13邢锯，之后將數(shù)值array擴(kuò)充到長(zhǎng)度為13，末尾添加的擴(kuò)充元素為原數(shù)值最后一個(gè)元素的值搀别。mid的取值與折半查找一樣丹擎，公式從(low + hig) / 2改為low + (F[k - 1] - 1)。
為什么要把數(shù)值長(zhǎng)度闊成到F[k] - 1呢歇父？
斐波那契的數(shù)組滿足：f[k] - 1 = (f[k - 1] + f[k - 2]) - 1蒂培，這個(gè)- 1的1就是mid，如果目標(biāo)在左區(qū)榜苫，數(shù)組長(zhǎng)度縮短到f[k - 1] 护戳，如果在右區(qū)，數(shù)組長(zhǎng)度縮短到f[k - 2]) - 1垂睬，同樣f[k - 1]) - 1 = (f[k - 2] + f[k - 3]) - 1媳荒，是一個(gè)遞歸的分割。
算法：

static int FibonacciSearch(int [] a, int n, int key) {
    int [] F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34};
    int low, high, mid, i, k;
    low = 1;
    high = n;
    k = 0;
    while (n > F[k]-1)  {/* 計(jì)算n位于斐波那契數(shù)列的位置 */
        k++;
    }
    while (low <= high) {
        mid = low + F[k-1] -1;
        if (key < a[mid]){
            high = mid - 1;
            k = k - 1;
        }
        else if (key > a[mid]) {
            low = mid + 1;
            k = k - 2;
        }
        else {
            if (mid <= n)
                return mid;
            else
                return n;
        }
    }
    return 0;
}

斐波那契查找的平均性能比折半查找好驹饺，但最壞情況下的性能卻比折半查找差钳枕，但是分割時(shí)只需進(jìn)行加、減運(yùn)算赏壹。

C.插值查找：根據(jù)給定值K來確定比較的關(guān)鍵字r[i].key的查找方法鱼炒。
打個(gè)比方，在英文字典里面查“apple”蝌借，你下意識(shí)翻開字典是翻前面的書頁還是后面的書頁呢昔瞧？如果再讓你查“zoo”指蚁，你又怎么查？很顯然自晰，這里你絕對(duì)不會(huì)是從中間開始查起凝化，而是有一定目的的往前或往后翻。
同樣的酬荞，比如要在取值范圍1 ~ 10000 之間 100 個(gè)元素從小到大均勻分布的數(shù)組中查找5缘圈， 我們自然會(huì)考慮從數(shù)組下標(biāo)較小的開始查找。
經(jīng)過以上分析袜蚕，折半查找這種查找方式糟把，還是有改進(jìn)空間的，并不一定是折半的牲剃。

image.png

image.png

image.png

即mid ≈ 1 + 0.153*(10 - 1) = 2.377取整得到mid = 2被辑，我們只需要兩次查找到結(jié)果了燎悍，顯著大大提高了查找的效率。
換句話說盼理，我們只需要在折半查找算法更改一行代碼就可以實(shí)現(xiàn)插值算法了谈山。

mid=low+(high-low)*(key-a[low])/(a[high]-a[low]); //插值

插值查找適用于關(guān)鍵字均勻分布的表，在這種情況下宏怔，對(duì)n值較大的順序表奏路，他的平均性能比折半查找好。