网站导航
> 技术文档 > 数据结构 查找算法详解（C语言）_c语言查找算法

数据结构 查找算法详解（C语言）_c语言查找算法

网友: 技术文档 2025-08-15 12:48:32

查找算法是数据结构中的核心内容，主要包括顺序查找、二分查找、哈希查找、树形查找等。下面我将详细介绍各种查找算法的原理、时间复杂度和C语言实现。

1. 顺序查找（Sequential Search）

原理：逐个遍历数据结构中的元素，直到找到目标元素或遍历完所有元素。

时间复杂度：

  • 最好情况：O(1)（目标元素在第一个位置）

  • 最坏情况：O(n)（目标元素在最后一个位置或不存在）

  • 平均情况：O(n)

C语言实现：

#include int sequentialSearch(int arr[], int n, int target) { for (int i = 0; i < n; i++) { if (arr[i] == target) { return i; // 返回目标元素的索引 } } return -1; // 未找到}int main() { int arr[] = {3, 7, 2, 9, 5, 1, 8}; int n = sizeof(arr) / sizeof(arr[0]); int target = 5; int index = sequentialSearch(arr, n, target); if (index != -1) { printf(\"元素 %d 在数组中的索引为: %d\\n\", target, index); } else { printf(\"元素 %d 不存在于数组中\\n\", target); } return 0;}

2. 二分查找（Binary Search）

原理：在有序数组中，通过不断缩小搜索范围来查找目标元素。

时间复杂度：O(log n)

适用条件：数组必须是有序的

C语言实现：

c

#include // 循环实现int binarySearch(int arr[], int n, int target) { int left = 0; int right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 if (arr[mid] == target) { return mid; } else if (arr[mid]  right) return -1; int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { return binarySearchRecursive(arr, mid + 1, right, target); } else { return binarySearchRecursive(arr, left, mid - 1, target); }}int main() { int arr[] = {1, 3, 5, 7, 9, 11, 13, 15}; int n = sizeof(arr) / sizeof(arr[0]); int target = 11; // 使用循环实现 int index1 = binarySearch(arr, n, target); printf(\"循环实现: 元素 %d 的索引: %d\\n\", target, index1); // 使用递归实现 int index2 = binarySearchRecursive(arr, 0, n-1, target); printf(\"递归实现: 元素 %d 的索引: %d\\n\", target, index2); return 0;}

3. 插值查找（Interpolation Search）

原理：在有序数组中，根据目标值的分布情况估算其位置，适用于均匀分布的有序数组。

时间复杂度：平均情况O(log log n)，最坏情况O(n)

C语言实现：

c

#include int interpolationSearch(int arr[], int n, int target) { int low = 0; int high = n - 1; while (low = arr[low] && target <= arr[high]) { // 计算插值位置 int pos = low + ((double)(high - low) / (arr[high] - arr[low])) * (target - arr[low]); if (arr[pos] == target) { return pos; } else if (arr[pos] < target) { low = pos + 1; } else { high = pos - 1; } } return -1;}int main() { int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; int n = sizeof(arr) / sizeof(arr[0]); int target = 70; int index = interpolationSearch(arr, n, target); if (index != -1) { printf(\"元素 %d 在数组中的索引为: %d\\n\", target, index); } else { printf(\"元素 %d 不存在于数组中\\n\", target); } return 0;}

4. 二叉搜索树查找（BST Search）

原理：在二叉搜索树中，根据节点值的大小关系决定搜索路径。

时间复杂度：

  • 平均情况：O(log n)

  • 最坏情况：O(n)（树退化为链表）

C语言实现：

c

#include #include typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;} TreeNode;// 创建新节点TreeNode* createNode(int value) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->val = value; newNode->left = NULL; newNode->right = NULL; return newNode;}// 在BST中查找元素TreeNode* searchBST(TreeNode* root, int target) { if (root == NULL || root->val == target) { return root; } if (target val) { return searchBST(root->left, target); } else { return searchBST(root->right, target); }}// 插入元素到BSTTreeNode* insertBST(TreeNode* root, int value) { if (root == NULL) { return createNode(value); } if (value val) { root->left = insertBST(root->left, value); } else if (value > root->val) { root->right = insertBST(root->right, value); } return root;}// 中序遍历（验证BST）void inorderTraversal(TreeNode* root) { if (root != NULL) { inorderTraversal(root->left); printf(\"%d \", root->val); inorderTraversal(root->right); }}int main() { TreeNode* root = NULL; root = insertBST(root, 50); insertBST(root, 30); insertBST(root, 70); insertBST(root, 20); insertBST(root, 40); insertBST(root, 60); insertBST(root, 80); printf(\"BST中序遍历: \"); inorderTraversal(root); printf(\"\\n\"); int target = 60; TreeNode* result = searchBST(root, target); if (result != NULL) { printf(\"元素 %d 存在于BST中\\n\", target); } else { printf(\"元素 %d 不存在于BST中\\n\", target); } return 0;}

5. 哈希查找（Hash Search）

原理：通过哈希函数计算键值的位置，直接访问该位置。

时间复杂度：

  • 平均情况：O(1)

  • 最坏情况：O(n)（所有键值都冲突）

C语言实现：

c

#include #include #include #define TABLE_SIZE 100// 哈希表节点typedef struct HashNode { char* key; int value; struct HashNode* next;} HashNode;// 哈希表typedef struct { HashNode** table; int size;} HashTable;// 创建哈希表HashTable* createHashTable(int size) { HashTable* ht = (HashTable*)malloc(sizeof(HashTable)); ht->size = size; ht->table = (HashNode**)calloc(size, sizeof(HashNode*)); return ht;}// 哈希函数（简单示例）unsigned int hashFunction(char* key, int size) { unsigned int hash = 0; for (int i = 0; key[i] != \'\\0\'; i++) { hash = (hash * 31 + key[i]) % size; } return hash;}// 插入键值对void insert(HashTable* ht, char* key, int value) { unsigned int index = hashFunction(key, ht->size); // 创建新节点 HashNode* newNode = (HashNode*)malloc(sizeof(HashNode)); newNode->key = strdup(key); newNode->value = value; newNode->next = NULL; // 插入到链表头部 if (ht->table[index] == NULL) { ht->table[index] = newNode; } else { newNode->next = ht->table[index]; ht->table[index] = newNode; }}// 查找键值int search(HashTable* ht, char* key) { unsigned int index = hashFunction(key, ht->size); HashNode* current = ht->table[index]; while (current != NULL) { if (strcmp(current->key, key) == 0) { return current->value; } current = current->next; } return -1; // 未找到}int main() { HashTable* ht = createHashTable(TABLE_SIZE); // 插入一些键值对 insert(ht, \"apple\", 10); insert(ht, \"banana\", 20); insert(ht, \"orange\", 30); insert(ht, \"grape\", 40); // 查找测试 char* keys[] = {\"apple\", \"banana\", \"orange\", \"grape\", \"peach\"}; for (int i = 0; i < 5; i++) { int value = search(ht, keys[i]); if (value != -1) { printf(\"%s: %d\\n\", keys[i], value); } else { printf(\"%s: 未找到\\n\", keys[i]); } } return 0;}

6. 查找算法比较

算法 时间复杂度（平均） 时间复杂度（最坏） 空间复杂度 适用场景 顺序查找 O(n) O(n) O(1) 无序小数据集 二分查找 O(log n) O(log n) O(1) 有序数组 插值查找 O(log log n) O(n) O(1) 均匀分布的有序数组 二叉搜索树查找 O(log n) O(n) O(n) 动态数据集 哈希查找 O(1) O(n) O(n) 快速查找，键值对存储

7. 查找算法选择策略

  1. 小规模无序数据：顺序查找简单高效

  2. 有序数组：二分查找是最佳选择

  3. 均匀分布的有序数据：插值查找效率更高

  4. 动态数据集：二叉搜索树提供插入和查找的平衡

  5. 需要快速查找：哈希表提供平均O(1)的查找时间

  6. 内存受限：有序数组或二叉搜索树更节省空间

  7. 磁盘存储：B树或B+树更适合大规模数据存储

8. 高频考点及解题技巧

考点1：二分查找变体（查找第一个/最后一个位置）

c

// 查找第一个等于target的位置int firstOccurrence(int arr[], int n, int target) { int left = 0, right = n - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; right = mid - 1; // 继续在左侧查找 } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result;}// 查找最后一个等于target的位置int lastOccurrence(int arr[], int n, int target) { int left = 0, right = n - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { result = mid; left = mid + 1; // 继续在右侧查找 } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result;}

考点2：旋转排序数组中的搜索（LeetCode 33）

c

int searchRotatedArray(int nums[], int n, int target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } // 左半部分有序 if (nums[left] <= nums[mid]) { if (nums[left] <= target && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } // 右半部分有序 else { if (nums[mid] < target && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1;}

考点3：在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）

c

int* searchRange(int* nums, int numsSize, int target, int* returnSize) { *returnSize = 2; int* result = (int*)malloc(2 * sizeof(int)); result[0] = -1; result[1] = -1; if (numsSize == 0) return result; // 查找第一个位置 int left = 0, right = numsSize - 1; while (left = target) { right = mid - 1; } else { left = mid + 1; } } if (left < numsSize && nums[left] == target) { result[0] = left; } else { return result; } // 查找最后一个位置 right = numsSize - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] <= target) { left = mid + 1; } else { right = mid - 1; } } result[1] = right; return result;}

9. 查找算法优化技巧

  1. 哨兵技巧：在顺序查找中设置哨兵，减少比较次数

  2. 跳跃查找：在有序数组中，通过跳跃固定步长加速查找

  3. 斐波那契查找：使用黄金分割点代替二分查找的中点

  4. 布隆过滤器：用于快速判断元素不存在的情况

  5. 多级索引：对大数据集建立多级索引加速查找

10. 实际应用场景

  1. 数据库索引：B+树索引加速数据检索

  2. 编译器符号表：哈希表存储变量和函数信息

  3. 缓存系统：哈希表实现快速键值查找

  4. 拼写检查：字典树存储单词并快速检查

  5. 地理信息系统：R树加速空间数据查询

  6. 网络路由：最长前缀匹配算法加速IP查找

掌握这些查找算法及其实现，能够根据具体问题选择最合适的查找策略，是解决实际问题的关键能力。

网络标签：

相关问题