溫馨提示：全文14632字，因為文章長度問題 需要分五篇讀完 詳細文章可以進我主頁！

今天就把常見****查找算法也總結個通透， 還有詳細的代碼解釋， 真的是寫完這篇感覺腦子已經不是自己的了，還希望大家好好利用。

查找算法，顧名思義就是在一堆數據中查找到你想要的那個數據。 以下就介紹幾種常用的查找算法，幫助大家更好的了解其原理和使用場景。

1、線性查找

1.1、基本概念及適用場景

線性查找（Linear Search），也叫順序查找，是一種簡單的查找算法，適用于無序數組或鏈表中的元素查找。線性查找的原理是按順序依次掃描待查找的元素，直到找到目標元素或掃描完所有元素。

具體實現時，從數組的第一個元素開始逐個比較，如果找到目標元素，則返回其下標，否則返回未找到的標記（如-1）。如果數組中存在多個目標元素，則只會找到第一個。

線性查找的時間復雜度為O(n)，其中n是待查找元素的個數，最壞情況下需要掃描整個數組或鏈表。

線性查找適用于以下情況：

• 待查找的數據規模較小，或數據無序，或需要查詢的數據在數組或鏈表的末尾。
• 數據存儲在單向鏈表中，沒有下標的概念。

需要注意的是，線性查找的效率比較低，不適用于大規模的數據查詢。

1.2、代碼示例

#include 


int linearSearch(int arr[], int n, int x) {
    int i;
    for (i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;   // 找到了，返回元素下標
        }
    }
    return -1;  // 沒找到，返回-1
}


int main() {
    int arr[] = {10, 20, 30, 40, 50, 60};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 40;
    int result = linearSearch(arr, n, x);
    if (result == -1) {
        printf("元素 %d 不存在\\n", x);
    } else {
        printf("元素 %d 的下標是 %d\\n", x, result);
    }
    return 0;
}

在上述示例中，linearSearch()函數用于進行線性查找，參數 arr 表示要查找的數組，n 表示數組的長度，x 表示要查找的元素值。函數通過遍歷數組中的每個元素，找到目標元素就返回其下標，若未找到則返回 -1。在 main() 函數中，聲明數組并調用 linearSearch() 函數進行查找，最終輸出查找結果。

2、二分查找

2.1、基本原理及注意事項

二分查找（Binary Search），也稱折半查找，是一種常見的查找算法。它的 基本原理是在有序數組中查找目標元素，通過將目標元素與有序數組的中間元素進行比較，可以排除一半的元素，從而提高查找效率 。

二分查找適用于有序數組中的查找，可以用于查找具有單調性質的數據集合。其時間復雜度為 O(log n)，相對于線性查找的 O(n)，效率更高。但是，二分查找的前提是必須有序，如果需要頻繁的插入和刪除操作，那么維護有序性就需要額外的操作，會降低效率。

在使用二分查找時需要注意以下幾點：

1. 數組必須有序。
2. 二分查找只適用于靜態查找，即目標數組不經常變化。
3. 目標元素必須是可比較的，可以使用小于或大于操作符進行比較。
4. 二分查找的效率高于線性查找，但在小數據量的查找中，可能沒有線性查找快。

二分查找的應用場景包括查找有序數組中的特定元素、查找第一個大于或小于給定值的元素等。

需要注意的是，雖然二分查找是一種高效的查找算法，但是在實際開發中，有時候使用哈希表等其他數據結構也能達到更高的效率，所以需要根據具體的問題場景選擇合適的算法。

2.2、代碼示例

當在一個有序數組查找某個元素時，二分查找是一個很高效的算法。

#include 


int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;


        if (arr[mid] == x) {
            return mid;
        }
        if (arr[mid] > x) {
            return binarySearch(arr, l, mid - 1, x);
        }
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}


int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 7;
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1) {
        printf("元素不在數組中");
    } else {
        printf("元素在數組中的索引為：%d", result);
    }
    return 0;
}

該代碼實現了一個名為binarySearch的函數，該函數用于在一個有序數組中查找給定的元素。binarySearch函數的參數為待查找數組arr，數組左邊界l，數組右邊界r以及要查找的元素x。

在函數內部，首先通過計算中間元素的下標來將待查找區間分為兩部分。如果中間元素等于要查找的元素，則直接返回中間元素的下標。如果中間元素大于要查找的元素，則在左半部分進行遞歸查找。否則，在右半部分進行遞歸查找。

在main函數中，先定義了一個有序數組arr，以及要查找的元素x。然后，調用binarySearch函數查找給定元素，并將返回值保存在變量result中。如果result的值為-1，則說明要查找的元素不在數組中；否則，輸出要查找的元素在數組中的索引。

需要注意的是，二分查找算法要求待查找的數組必須是有序的。因此，在使用二分查找算法前，需要保證待查找的數組已經排好序。

3、插值查找

3.1、基本概念

插值查找是一種基于二分查找算法的優化，它的基本原理與二分查找類似，只不過插值查找根據查找鍵值與查找范圍內值的分布情況，通過插值來確定下一步查找的位置。與二分查找相比，它可以提供更快的查找速度，尤其是數據比較分散的情況下，比如數據集中在數組的前面或后面。

插值查找的具體實現步驟如下：

1. 確定查找范圍，初始化起始位置left為0，結束位置right為n-1，其中n為數組長度。
2. 計算中間位置mid，mid的值為 (key - arr[left]) / (arr[right] - arr[left]) * (right - left) + left，其中key為查找關鍵字，arr為待查找的有序數組。
3. 如果arr[mid]等于key，則返回mid。
4. 如果arr[mid]小于key，則在[mid+1, right]范圍內查找。
5. 如果arr[mid]大于key，則在[left, mid-1]范圍內查找。
6. 重復2-5步，直到查找到目標值或查找范圍為空，查找失敗。

需要注意的是，插值查找要求待查找的數組是有序的，否則無法保證查找結果的正確性。 此外，當數據分布較為均勻時，插值查找可以快速定位到目標值，但當數據分布不均時，可能會導致查找效率的降低。

3.2、代碼示例

#include 


// 插值查找函數，array為待查找數組，n為數組長度，target為目標值
int interpolationSearch(int array[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high && target >= array[low] && target <= array[high]) {
        int pos = low + ((double)(target - array[low]) / (array[high] - array[low])) * (high - low);
        if (array[pos] == target) {
            return pos;
        } else if (array[pos] < target) {
            low = pos + 1;
        } else {
            high = pos - 1;
        }
    }
    return -1;
}


// 測試
int main() {
    int array[] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
    int n = sizeof(array) / sizeof(int);
    int target = 12;
    int index = interpolationSearch(array, n, target);
    if (index != -1) {
        printf("目標值%d在數組中的位置是%d\\n", target, index);
    } else {
        printf("目標值%d在數組中不存在\\n", target);
    }
    return 0;
}

在上面的代碼中，interpolationSearch() 函數采用了插值查找算法的實現，其中 array 為待查找數組，n 表示數組長度，target 表示目標值。在查找過程中，我們首先計算出目標值所在的估計位置 pos，然后根據 array[pos] 的值與目標值 target 的大小進行比較，并更新查找的范圍，直到找到目標值或者確定目標值不存在于數組中。最終，該函數返回目標值在數組中的位置，如果不存在則返回 -1。

在 main() 函數中，我們定義了一個數組 array 和目標值 target，并調用 interpolationSearch() 函數進行查找，將結果輸出到控制臺。