【顺序表查找 顺序查找、二分查找 C语言实现】在数据结构与算法中，查找是常见的操作之一。顺序表作为线性表的一种存储结构，其查找方式主要包括顺序查找和二分查找两种。本文将详细介绍这两种查找方法的原理，并提供基于C语言的实现代码。
一、顺序查找
顺序查找，也称为线性查找，是一种最基础的查找方法。它从表的一端开始，逐个比较元素，直到找到目标值或遍历完整个表为止。
1.1 算法思想
- 从表的第一个元素开始，依次与目标值进行比较。
- 如果找到相等的元素，则返回该元素的位置。
- 如果遍历完所有元素仍未找到，则返回查找失败。
1.2 时间复杂度
- 最坏情况：O(n)
- 平均情况：O(n)
1.3 C语言实现
```c
include
int sequential_search(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i; // 找到，返回下标
}
}
return -1; // 未找到
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 30;
int result = sequential_search(arr, n, key);
if (result != -1) {
printf("元素 %d 在数组中的位置为：%d\n", key, result);
} else {
printf("元素 %d 未找到。\n", key);
}
return 0;
}
```
二、二分查找
二分查找，又称折半查找，是一种效率较高的查找方法。它要求被查找的数据必须是有序的。
2.1 算法思想
- 首先确定中间位置mid。
- 比较中间元素与目标值：
- 如果相等，直接返回；
- 如果目标值小于中间元素，则在左半部分继续查找；
- 如果目标值大于中间元素，则在右半部分继续查找。
- 重复上述过程，直到找到目标值或查找范围为空。
2.2 时间复杂度
- 最坏情况：O(log₂n)
- 平均情况：O(log₂n)
2.3 C语言实现
```c
include
int binary_search(int arr[], int n, int key) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) {
return mid; // 找到，返回下标
} else if (arr[mid] < key) {
low = mid + 1; // 在右半部分查找
} else {
high = mid - 1; // 在左半部分查找
}
}
return -1; // 未找到
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 30;
int result = binary_search(arr, n, key);
if (result != -1) {
printf("元素 %d 在数组中的位置为：%d\n", key, result);
} else {
printf("元素 %d 未找到。\n", key);
}
return 0;
}
```
三、总结
顺序查找和二分查找是两种典型的查找算法，适用于不同的场景：
- 顺序查找适用于无序数据，实现简单但效率较低。
- 二分查找适用于有序数据，效率高但需先排序。
在实际应用中，应根据数据的特性选择合适的查找方法。对于大规模数据，建议使用更高效的查找结构，如哈希表或平衡二叉树。
通过以上代码示例，读者可以直观地理解这两种查找算法的实现方式，并根据需要进行扩展和优化。
