有序数组的两个应用
前面我们学习了数组的排序方法,通常我们对数组排序不是为了排序而排序,而是为了其它的用途才排序的,这里了解一下有序数组的两个常见应用。
二分查找
二分查找也称为折半查找,它的前提是数组中的元素是有序的。算法过程如下(假定数组为升序):先拿要查找的元素与数组中间位置的元素相比较,如果小
于则在数组的前半部分查找,大于则在数组的后半部分查找,相等则在找到了。重复这个过程直到找到或者数组被分成单个元素为止。实现如下:
int qsearch(void** array, size_t nr, void* data, DataCompareFunc cmp)
{
int low = 0;
int mid = 0;
int high = nr-1;
int result = 0;
return_val_if_fail(array != NULL && cmp != NULL, -1);
while(low <= high)
{
mid = low + ((high - low) >> 1);
result = cmp(array[mid], data);
if(result == 0)
{
return mid;
}
else if(result < 0)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}
在编写二分查找的代码时,除了算法本身外还要注意两个问题:
o 计算中间位置的方法。这里使用mid = low + ((high - low) >> 1)代替(low+hign)/2,目的是为了避免整数溢出和除法计算。
o 边界值问题。在编写排序和查找的程序时,最容易犯边界值错误,写程序时一定要保持思路清晰。不防模拟计算机去执行你写的程序,用不同的输入观察所得的结果,最后加上自动测试,可以大大减少出错的概率。
去除重复元素
在工作中,我经常使用linux中的命令sort和uniq的组合。uniq的功能是去除重复的元素,它的前提也是要求数据是有序的。下面我们写一个程序,它打印数组中不重复元素(整数):
Ret unique_print_int(void* ctx, void* data)
{
if(*(int*)ctx != (int)data)
{
*(int*)ctx = (int)data;
printf("%d ", (int)data);
}
return RET_OK;
}
darray_foreach(darray, unique_print_int, &data);
注意:记得把data初始化成不等于第一个元素的值,否则可能漏打第一个元素。这个算法当然同样适用链表,只要是有序的即可。
本节示例代码请到这里下载。
分享到:
相关推荐
简历模板-程序员-通用-精选简历模板-程序员-通用-精选简历模板-程序员-通用-精选简历模板-程序员-通用-精选简历模板-程序员-通用-精选简历模板-程序员-通用-精选简历模板-程序员-通用-精选简历模板-程序员-通用-精选...
《系统程序员成长计划》_C语言_源码.zip
程序员简历模板-软件工程师程序员简历模板-软件工程师程序员简历模板-软件工程师程序员简历模板-软件工程师程序员简历模板-软件工程师程序员简历模板-软件工程师程序员简历模板-软件工程师程序员简历模板-软件工程师...
《程序员成长课堂--PHP标准教程》这本书所有章节案例的源代码。
WINDOWS程序员指南1--DLL和内存管理
WINDOWS程序员使用指南--OLE-DDE WINDOWS程序员使用指南--OLE-DDE
黑马程序员 - Java基础教学 - 04 - 数组、进制转换、二维数组
JAVA程序员之路-----看专业程序员的成长之路
程序员考试试题---程序员考试教程 程序员考试试题---程序员考试教程
C++Builder程序员成长攻略 书中源代码
资源名称:程序员简历模板-简约水墨风格-动态ppt模板-高端大气上档次.pptx 内容概要:是一款程序员简历模板,有音乐有图片,动态ppt模板-高端大气上档次,低调奢华有内涵。直接替换文件中的内容即可二次编辑。特别...
WINDOWS程序员使用指南--资源 WINDOWS程序员使用指南--资源
《DB2程序员成长攻略》-龚涛-源代码《DB2程序员成长攻略》-龚涛-源代码