C 中的尋找演算法與應用實例
在 C 中，尋找演算法是指在一組資料中尋找特定元素的演算法。它是電腦程式中最基礎、最常用的演算法之一，廣泛應用於各種實際問題。本文將介紹 C 中常用的幾種查找演算法，並給出對應的應用實例，以幫助讀者更好地理解和掌握這些演算法。
一、線性查找演算法
線性查找演算法（也稱為順序查找演算法）是最簡單、最基礎的查找演算法。它的基本想法是從資料的第一個元素開始逐一比較，直到找到目標元素為止。以下是 C 中實作線性查找的程式碼：
int linearSearch(int arr[], int n, int x) { for (int i = 0; i < n; i++) { if (arr[i] == x) { return i; // 找到目标元素返回其下标 } } return -1; // 未找到目标元素返回 -1 }
線性查找演算法的時間複雜度為 O(n)，其中 n 表示資料的規模，即資料中元素的數量。如果待查找的元素恰好在資料中的最後一個位置，那麼線性查找需要遍歷整個資料才能找到目標元素，時間複雜度就會達到 O(n) 的最壞情況。因此，當資料規模很大時，線性查找演算法效率並不高。
二、二分查找演算法
二分查找演算法（也稱為折半查找演算法）是一種高效率的查找演算法。它要求資料必須是有序的，並且透過每次查找中折半的方式減少查找的範圍，最終找到目標元素。以下是 C 中實作二分查找的程式碼：
int binarySearch(int arr[], int n, int x) { int left = 0, right = n - 1, mid; while (left <= right) { mid = (left + right) / 2; if (arr[mid] == x) { return mid; // 找到目标元素返回其下标 } else if (arr[mid] > x) { right = mid - 1; // 目标元素在左边区域 } else { left = mid + 1; // 目标元素在右边区域 } } return -1; // 未找到目标元素返回 -1 }
二分查找演算法的時間複雜度為 O(log n)，其中 n 表示資料的規模，也就是資料中元素的數量。二分查找演算法利用了有序資料的特點，每次查找可以將查找範圍折半，從而快速找到目標元素。但是，當資料不是有序的時候，需要先進行排序才能使用二分查找，這會增加額外的時間複雜度。
三、雜湊查找演算法
雜湊查找演算法（也稱為雜湊查找演算法）是一種利用雜湊函數快速尋找的演算法。它透過將資料元素映射為一個固定的位置（即雜湊值），從而快速找到目標元素。以下是 C 中實作哈希查找的程式碼：
const int MAX_SIZE = 10007; // 哈希表的最大长度 struct Node { int key, value; // 哈希表中存放的元素 Node* next; // 指向下一个节点的指针 }; class HashTable { private: Node* table[MAX_SIZE]; // 哈希表的数组 int hashFunc(int key) { return key % MAX_SIZE; } // 哈希函数 public: HashTable() { memset(table, 0, sizeof(table)); } // 初始化哈希表 void insert(int key, int value) // 将元素插入哈希表 { int pos = hashFunc(key); Node* p = new Node(); p->key = key; p->value = value; p->next = table[pos]; table[pos] = p; } int search(int key) // 在哈希表中查找元素 { int pos = hashFunc(key); Node* p = table[pos]; while (p != NULL) { if (p->key == key) { return p->value; // 找到目标元素返回其值 } p = p->next; } return -1; // 未找到目标元素返回 -1 } };
哈希查找演算法的時間複雜度為 O(1)，不受資料規模的影響，具有很高的效率。但是，在雜湊函數的設計上需要考慮因子較多，如果雜湊函數不好，可能會造成雜湊衝突，進而影響查找效率。
四、查找演算法的應用實例
除了以上三種查找演算法，C 中還有很多其他的查找演算法，例如插值查找、斐波那契查找等。下面給出一個簡單的應用實例，展示查找演算法在實際問題中的應用。
給定一個陣列和一個目標值，在陣列中找到兩個數的和等於目標值，傳回兩個數的下標。以下是C 中實現該功能的程式碼：
