4、斐波那契查找

4.1、基本原理

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

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

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

4.2、代碼示例

方法一：

假設需要查找的元素為key，數組為arr，數組長度為n

#include 
#include 


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


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


    // 對數組進行擴展，使其長度為斐波那契數列中的某個數
    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) {
        // 計算當前中間位置
        mid = low + fib1 - 1;
        // 如果key比當前位置的值小，則在左側繼續查找
        if (key < tmp[mid]) {
            high = mid - 1;
            fibn = fib1;
            fib1 = fib2 - fib1;
            fib2 = fibn - fib1;
        }
        // 如果key比當前位置的值大，則在右側繼續查找
        else if (key > tmp[mid]) {
            low = mid + 1;
            fibn = fib2;
            fib1 = fib1 - fib2;
            fib2 = fibn - fib1;
        }
        // 找到了key
        else {
            // 如果當前位置小于n，則返回該位置，否則返回n-1
            if (mid < n) {
                return mid;
            } else {
                return n - 1;
            }
        }
    }


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


// 測試代碼
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;
}

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

方法二：

#include 


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


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


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


    // 將數組擴展到斐波那契數列中第k個數的長度
    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 在數組中的位置為 %d\\n", key, pos);
    } else {
        printf("元素 %d 在數組中不存在\\n", key);
    }
    return 0;
}

在這段代碼中，我們首先使用 getFibonacci 函數獲取斐波那契數列中第k個數，然后將數組 a 擴展到斐波那契數列中第k個數的長度，這樣做是為了保證數組長度大于等于斐波那契數列中第k個數，從而可以用斐波那契數列中的數作為分割點進行查找。最后，我們使用二分查找的方式進行查找，最終返回查找結果的下標或者-1表示查找失敗。

5、哈希查找

5.1、基本原理

哈希查找是一種常用的查找算法，它的基本思想是將數據元素映射到一個固定的存儲位置，從而實現快速的查找。哈希查找的基本原理是利用哈希函數將關鍵字映射到存儲位置，當需要查找一個元素時，先通過哈希函數計算出該元素對應的存儲位置，然后在該位置進行查找。

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

哈希查找的注意事項包括以下幾點：

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

5.2、代碼示例

下面是一個簡單的哈希查找算法的代碼示例，使用了線性探測法解決沖突。

#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;
}

該代碼實現了一個基于線性探測法的哈希查找算法，其中 HashTable 表示哈希表，HashNode 表示哈希表中的一個節點，包括鍵 key 和值 value，hash 函數用于計算哈希值，createHashTable 函數用于創建一個新的哈希表，insert 函數用于在哈希表中插入一個節點，search 函數用于在哈希表中查找指定的鍵，并返回對應的值，delete 函數用于從哈希表中刪除指定的鍵。