4、斐波那契查找

4.1、基本原理

斐波那契查找算法（Fibonacci Search Algorithm）是一種利用斐波那契數(shù)列長(zhǎng)度的有序數(shù)組進(jìn)行查找的算法。與二分查找不同，斐波那契查找每次的查找范圍是斐波那契數(shù)列中的某一段，從而更加高效地進(jìn)行查找。

具體來說，假設(shè)待查找的數(shù)組為arr，數(shù)組長(zhǎng)度為n。斐波那契查找首先要確定一個(gè)斐波那契數(shù)列fib，滿足fib[k] >= n，且fib[k-1] < n。然后根據(jù)當(dāng)前查找范圍的左右端點(diǎn)計(jì)算mid = left + fib[k-1]，即查找范圍中點(diǎn)的位置。如果arr[mid] == target，則查找成功；如果arr[mid] < target，則在mid的右側(cè)繼續(xù)查找；如果arr[mid] > target，則在mid的左側(cè)繼續(xù)查找。查找的過程類似于二分查找，只不過查找范圍不是一半，而是根據(jù)斐波那契數(shù)列劃分的一段。

斐波那契查找的優(yōu)點(diǎn)是可以在O(log n)的時(shí)間內(nèi)完成查找，比一般的線性查找O(n)和二分查找O(log n)更快。但是需要注意的是，斐波那契查找算法只適用于元素?cái)?shù)量比較大、分布均勻的數(shù)組。對(duì)于元素?cái)?shù)量較少或分布不均的數(shù)組，效率并不一定比其他算法高。

4.2、代碼示例

方法一：

假設(shè)需要查找的元素為key，數(shù)組為arr，數(shù)組長(zhǎng)度為n

#include 
#include 


// 斐波那契查找算法
int fib_search(int arr[], int n, int key) {
    // 初始化斐波那契數(shù)列
    int fib1 = 0;
    int fib2 = 1;
    int fibn = fib1 + fib2;


    // 找到斐波那契數(shù)列中第一個(gè)大于等于n的數(shù)
    while (fibn < n) {
        fib1 = fib2;
        fib2 = fibn;
        fibn = fib1 + fib2;
    }


    // 對(duì)數(shù)組進(jìn)行擴(kuò)展，使其長(zhǎng)度為斐波那契數(shù)列中的某個(gè)數(shù)
    int *tmp = (int *)malloc(fibn * sizeof(int));
    for (int i = 0; i < n; i++) {
        tmp[i] = arr[i];
    }
    for (int i = n; i < fibn; i++) {
        tmp[i] = arr[n - 1];
    }


    // 開始查找
    int low = 0;
    int high = fibn - 1;
    int mid;
    while (low <= high) {
        // 計(jì)算當(dāng)前中間位置
        mid = low + fib1 - 1;
        // 如果key比當(dāng)前位置的值小，則在左側(cè)繼續(xù)查找
        if (key < tmp[mid]) {
            high = mid - 1;
            fibn = fib1;
            fib1 = fib2 - fib1;
            fib2 = fibn - fib1;
        }
        // 如果key比當(dāng)前位置的值大，則在右側(cè)繼續(xù)查找
        else if (key > tmp[mid]) {
            low = mid + 1;
            fibn = fib2;
            fib1 = fib1 - fib2;
            fib2 = fibn - fib1;
        }
        // 找到了key
        else {
            // 如果當(dāng)前位置小于n，則返回該位置，否則返回n-1
            if (mid < n) {
                return mid;
            } else {
                return n - 1;
            }
        }
    }


    // 沒有找到key
    free(tmp);
    return -1;
}


// 測(cè)試代碼
int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 7;
    int index = fib_search(arr, n, key);
    if (index == -1) {
        printf("The key %d is not found.\\n", key);
    } else {
        printf("The key %d is found at index %d.\\n", key, index);
    }
    return 0;
}

注意：上述代碼假設(shè)數(shù)組中的元素是按照從小到大的順序排列的。如果數(shù)組中的元素是無序的，則需要先對(duì)數(shù)組進(jìn)行排序，然后再進(jìn)行斐波那契查找。

方法二：

#include 


// 獲取斐波那契數(shù)列，n表示數(shù)列中第n個(gè)元素的值
int getFibonacci(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return getFibonacci(n-1) + getFibonacci(n-2);
}


// 斐波那契查找算法，a為有序數(shù)組，n為數(shù)組長(zhǎng)度，key為要查找的元素
int fibonacciSearch(int a[], int n, int key) {
    int low = 0, high = n-1, k = 0, mid = 0;


    // 計(jì)算斐波那契數(shù)列中第k個(gè)數(shù)剛好大于n
    while (n > getFibonacci(k)-1) {
        k++;
    }


    // 將數(shù)組擴(kuò)展到斐波那契數(shù)列中第k個(gè)數(shù)的長(zhǎng)度
    int *temp = new int[getFibonacci(k)];
    for (int i = 0; i < n; i++) {
        temp[i] = a[i];
    }
    for (int i = n; i < getFibonacci(k); i++) {
        temp[i] = a[n-1];
    }


    // 二分查找
    while (low <= high) {
        mid = low + getFibonacci(k-1) - 1;
        if (key < temp[mid]) {
            high = mid - 1;
            k--;
        } else if (key > temp[mid]) {
            low = mid + 1;
            k -= 2;
        } else {
            if (mid < n) {
                return mid;
            } else {
                return n - 1;
            }
        }
    }
    delete [] temp;
    return -1;
}


int main() {
    int a[] = {1, 3, 5, 7, 9, 11, 13};
    int n = sizeof(a) / sizeof(a[0]);
    int key = 11;
    int pos = fibonacciSearch(a, n, key);
    if (pos >= 0) {
        printf("元素 %d 在數(shù)組中的位置為 %d\\n", key, pos);
    } else {
        printf("元素 %d 在數(shù)組中不存在\\n", key);
    }
    return 0;
}

在這段代碼中，我們首先使用 getFibonacci 函數(shù)獲取斐波那契數(shù)列中第k個(gè)數(shù)，然后將數(shù)組 a 擴(kuò)展到斐波那契數(shù)列中第k個(gè)數(shù)的長(zhǎng)度，這樣做是為了保證數(shù)組長(zhǎng)度大于等于斐波那契數(shù)列中第k個(gè)數(shù)，從而可以用斐波那契數(shù)列中的數(shù)作為分割點(diǎn)進(jìn)行查找。最后，我們使用二分查找的方式進(jìn)行查找，最終返回查找結(jié)果的下標(biāo)或者-1表示查找失敗。

5、哈希查找

5.1、基本原理

哈希查找是一種常用的查找算法，它的基本思想是將數(shù)據(jù)元素映射到一個(gè)固定的存儲(chǔ)位置，從而實(shí)現(xiàn)快速的查找。哈希查找的基本原理是利用哈希函數(shù)將關(guān)鍵字映射到存儲(chǔ)位置，當(dāng)需要查找一個(gè)元素時(shí)，先通過哈希函數(shù)計(jì)算出該元素對(duì)應(yīng)的存儲(chǔ)位置，然后在該位置進(jìn)行查找。

哈希函數(shù)是哈希查找的關(guān)鍵，它將關(guān)鍵字映射到一個(gè)存儲(chǔ)位置。哈希函數(shù)應(yīng)該具有良好的映射性能，能夠均勻地將關(guān)鍵字分布到不同的存儲(chǔ)位置上，這樣可以避免沖突。沖突是指多個(gè)關(guān)鍵字映射到同一個(gè)存儲(chǔ)位置上，這種情況下需要解決沖突。

哈希查找的注意事項(xiàng)包括以下幾點(diǎn)：

1. 哈希函數(shù)的設(shè)計(jì)應(yīng)該具有良好的均勻性，能夠盡可能避免沖突。
2. 解決沖突的方法有很多，比如拉鏈法、開放地址法等。選擇合適的沖突解決方法對(duì)哈希查找的效率影響很大。
3. 哈希查找的效率取決于哈希函數(shù)的設(shè)計(jì)、沖突解決方法的選擇以及負(fù)載因子等因素。
4. 哈希表的大小應(yīng)該合適，過大會(huì)造成空間浪費(fèi)，過小會(huì)造成沖突增加。
5. 哈希表的擴(kuò)容和縮容是一個(gè)比較復(fù)雜的問題，需要根據(jù)實(shí)際情況進(jìn)行考慮。

5.2、代碼示例

下面是一個(gè)簡(jiǎn)單的哈希查找算法的代碼示例，使用了線性探測(cè)法解決沖突。

#include 
#include 


#define TABLE_SIZE 13


typedef struct HashNode {
    int key;
    int value;
} HashNode;


typedef struct HashTable {
    HashNode *table[TABLE_SIZE];
} HashTable;


int hash(int key) {
    return key % TABLE_SIZE;
}


HashTable* createHashTable() {
    HashTable *hashTable = (HashTable*)malloc(sizeof(HashTable));
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable->table[i] = NULL;
    }
    return hashTable;
}


void insert(HashTable *hashTable, int key, int value) {
    HashNode *node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->value = value;


    int index = hash(key);
    while (hashTable->table[index] != NULL) {
        index = (index + 1) % TABLE_SIZE;
    }
    hashTable->table[index] = node;
}


int search(HashTable *hashTable, int key) {
    int index = hash(key);
    while (hashTable->table[index] != NULL && hashTable->table[index]->key != key) {
        index = (index + 1) % TABLE_SIZE;
    }


    if (hashTable->table[index] == NULL) {
        return -1;
    } else {
        return hashTable->table[index]->value;
    }
}


void delete(HashTable *hashTable, int key) {
    int index = hash(key);
    while (hashTable->table[index] != NULL && hashTable->table[index]->key != key) {
        index = (index + 1) % TABLE_SIZE;
    }


    if (hashTable->table[index] != NULL) {
        free(hashTable->table[index]);
        hashTable->table[index] = NULL;
    }
}


int main() {
    HashTable *hashTable = createHashTable();
    insert(hashTable, 3, 100);
    insert(hashTable, 9, 200);
    insert(hashTable, 6, 300);
    insert(hashTable, 12, 400);


    int value = search(hashTable, 9);
    printf("Value: %d\\n", value);


    delete(hashTable, 9);


    value = search(hashTable, 9);
    printf("Value: %d\\n", value);


    return 0;
}

該代碼實(shí)現(xiàn)了一個(gè)基于線性探測(cè)法的哈希查找算法，其中 HashTable 表示哈希表，HashNode 表示哈希表中的一個(gè)節(jié)點(diǎn)，包括鍵 key 和值 value，hash 函數(shù)用于計(jì)算哈希值，createHashTable 函數(shù)用于創(chuàng)建一個(gè)新的哈希表，insert 函數(shù)用于在哈希表中插入一個(gè)節(jié)點(diǎn)，search 函數(shù)用于在哈希表中查找指定的鍵，并返回對(duì)應(yīng)的值，delete 函數(shù)用于從哈希表中刪除指定的鍵。