德阳网站制作公司,做资源网站怎么不封,wordpress可视化主题制作,广东省东莞市有几个区引言
在计算机科学领域#xff0c;查找是一项基本操作#xff0c;而二分查找是一种高效的查找算法。本博客将详细解释一个简单的C语言程序#xff0c;演示如何使用标准库函数qsort和bsearch来对一个整数数组进行排序和二分查找。
代码解析
包含头文件
#include stdi…引言
在计算机科学领域查找是一项基本操作而二分查找是一种高效的查找算法。本博客将详细解释一个简单的C语言程序演示如何使用标准库函数qsort和bsearch来对一个整数数组进行排序和二分查找。
代码解析
包含头文件
#include stdio.h
#include stdlib.h首先我们包含了两个标准头文件stdio.h用于输入输出操作stdlib.h用于内存分配和其他一些杂项功能。
比较函数
int compareIntegers(const void *a, const void *b) {return (*(int *)a - *(int *)b);
}定义了一个比较函数compareIntegers该函数用于在排序和二分查找时比较两个整数。这个函数的作用是返回a - b的值即升序排序。
主函数
int main() {// 创建已排序的整数数组int numbers[] {101, 305, 248, 407, 109};int numNumbers sizeof(numbers) / sizeof(numbers[0]);// 排序数组qsort(numbers, numNumbers, sizeof(numbers[0]), compareIntegers);// 设置要查找的 numberint targetNumber 305;// 使用bsearch搜索学生int *result (int *)bsearch(targetNumber, numbers, numNumbers, sizeof(numbers[0]), compareIntegers);// 检查结果并输出if (result ! NULL) {printf(Number found: %d\n, *result);} else {printf(Number %d not found\n, targetNumber);}return 0;
}创建并排序数组
int numbers[] {101, 305, 248, 407, 109};
int numNumbers sizeof(numbers) / sizeof(numbers[0]);
qsort(numbers, numNumbers, sizeof(numbers[0]), compareIntegers);在主函数中我们首先创建了一个整数数组numbers然后使用sizeof操作符计算数组元素个数。接下来我们使用qsort函数对数组进行升序排序传递了比较函数compareIntegers来定义排序顺序。
二分查找
int targetNumber 305;
int *result (int *)bsearch(targetNumber, numbers, numNumbers, sizeof(numbers[0]), compareIntegers);设置要查找的目标数字为305然后使用bsearch函数在已排序的数组中进行二分查找。同样我们传递了比较函数compareIntegers来确保查找的一致性。
输出结果
if (result ! NULL) {printf(Number found: %d\n, *result);
} else {printf(Number %d not found\n, targetNumber);
}最后我们检查bsearch的结果。如果找到了目标数字就输出找到的数字否则输出未找到的消息。
时间复杂度
让我们分析一下这个程序中排序和查找部分的时间复杂度 排序 (qsort) 时间复杂度O(n * log(n)) qsort通常使用快速排序算法其平均时间复杂度为O(n * log(n))其中n是数组的元素个数。在这个程序中numNumbers是5所以排序的时间复杂度为O(5 * log(5))。 查找 (bsearch) 时间复杂度O(log(n)) bsearch使用二分查找算法其时间复杂度为O(log(n))其中n是数组的元素个数。在这个程序中数组已经排好序numNumbers是5所以查找的时间复杂度为O(log(5))。
因此整个程序的时间复杂度主要由排序的部分决定为O(5 * log(5))。在大O表示法中忽略常数项这可以简化为O(log(5))即O(1)。因此总体时间复杂度可以近似看作是O(1)即常数时间。这意味着程序的运行时间与数组的规模无关对于小规模的数组来说是非常高效的。
总结
这个简单的C程序演示了如何使用qsort对数组进行排序然后使用bsearch进行二分查找。这两个函数是C标准库中用于排序和查找的强大工具通过传递比较函数我们可以适应不同的数据类型和排序/查找需求。在实际编程中这种方法能够提高效率并且是一种常见的编程实践。
