频道栏目
首页 > 程序开发 > Web开发 > PHP教程 > PHP应用 > 代码收藏 > 正文
IOS算法(五)之折半查找
2016-01-07 14:15:44           
收藏   我要投稿

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

折半查找法的两种实现

折半查找法思想:

在有序表中,把待查找数据值与查找范围的中间元素值进行比较,会有三种情况出现:

1)待查找数据值与中间元素值正好相等,则放回中间元素值的索引。

2)待查找数据值比中间元素值小,则以整个查找范围的前半部分作为新的查找范围,执行1),直到找到相等的值。

3)待查找数据值比中间元素值大,则以整个查找范围的后半部分作为新的查找范围,执行1),直到找到相等的值

4)如果最后找不到相等的值,则返回错误提示信息。

按照二叉树来理解:中间值为二叉树的根,前半部分为左子树,后半部分为右子树。折半查找法的查找次数正好为该值所在的层数。等概率情况下,约为 log2(n+1)-1


代码实现:

// main.m

//算法----折半查找

// Copyright (c) 2014年summer2014mht@sina.com. All rights reserved.

#import

intmain(intargc,constchar* argv[])

{

intarray[] = {0,1,2,3,4,5,6,7,8,9,10};

intcount =sizeof(array) /sizeof(array[0]);

inttarget =10;

intstart =0, end = count -1, mid =0;

while(start <= end) {

mid = (start + end) /2;

if(array[mid] > target) {

end = mid -1;

}elseif(array[mid] < target) {

start = mid +1;

}else{

break;

}

}

if(start <= end) {

printf("[%d]: %d\n", mid, array[mid]);

}else{

printf("not found\n");

}

return0;

}

点击复制链接 与好友分享!回本站首页
相关TAG标签 算法
上一篇:OpenGL之路(十)绚丽的移动动画
下一篇:LightOJ
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站