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 中實現該功能的程式碼：
