免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: OwnWaterloo

[算法][C]二叉搜索树的两路二分查找 [复制链接]

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-04 23:33 |显示全部楼层
回复 59# yulihua49

stl接口比较保守。比较器的粒度是map的类型,也就是instances的整个生命周期。
对用户来说,升序还是降序一开始就决定好了。【对stl来说始终是按compare的升序】
不过也够了:
1. > k 的元素是[m.upper_bound(k), m.end())
2. >= k 的元素是[m.lower_bound(k), m.end())
3. < k 的元素是[m.begin(), m.lower_bound(k))
4. <= k 的元素是[m.begin(), m.upper_bound(k))


至于后缀下划线区分度不够明显的问题,因为是随手写的代码,没过多想命名的问题。这在一开始就说了。
即使后缀下划线代表私有不是C/C++社区的共识,static代表私有总该是共识了。
最后,我至于那么傻先去找最右节点吗。。。找出来了能干嘛。。。

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-04 23:44 |显示全部楼层
yulihua49 发表于 2012-08-04 22:51
习惯问题,一般把有序数组叫二分法,二叉链表叫二叉树,以示方法上的区别,习惯了你的称谓方法,理解上也没问题。
系统的Binary_search(怎么拼写的一时忘了)也是指的对数组的查找。


怎么我知道的二分就不局限于数组或是树呢?
因为有序,所以可以根据对一个元素的判断推断出并省略对其他元素的判断
至于有序序列是数组形式,还是树形式,还是什么其他形式,与二分根本就无关。
STL对链表都可以二分查找,并且一定保证只有对数次比较。 只是因为链表的特殊性,就不能保证对数次的元素访问而已。



yulihua49 发表于 2012-08-04 22:51
试了各种方法,就是二叉树快,所以就向人推荐,也没有错啊。这也不涉及我会什么,不会什么,即使我什么都不会,各种工具系统里都有,拿来用就是。
你从文件里读出一堆数据,把他们摆好了(摆也是个难事,不知道要多大空间),再排序;还是边读边往树里插(节点自动分配),读完了,序也排好了,哪个快?

  1. vector<int> v(istream_iterator<int>(cin), (istream_iterator<int>()));
  2. v.sort();
  3. copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
复制代码

  1. multiset<int> s(istream_iterator<int>(cin), (istream_iterator<int>()));
  2. copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
复制代码
我还真不信后者会比前者快。

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-04 23:52 |显示全部楼层
本帖最后由 OwnWaterloo 于 2012-08-04 23:54 编辑

回复 62# OwnWaterloo

而且不说提问那些人的人大多数都暗含有"在一个已经准备好(读入完成)的数组上排序"这一条件。
类似上面的代码,如果预先分配 —— 比如加一个适度的reserve —— 甚至预先读取完成,根本就没什么好比较的。

即使没有这个条件,节点型容器附加开销,内存分散程度依赖分配器的实现导致局部性差的问题明摆着,怎么会遇见个问排序的帖子就推荐用它来排序?

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-08-05 13:30 |显示全部楼层
ow你既然降到了二分查找,怎么不讲讲循环不变式在设计二分查找时的应用呢?

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-07 19:30 |显示全部楼层
回复 64# starwing83

循环不变式?是那个循环前满足xx,yy,zz...性质,循环后依然保持xx,yy,zz..总之目的是为了证明算法正确的那个东西么?
术语真是让人既爱又恨的东西……

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-08-07 20:04 |显示全部楼层
回复 65# OwnWaterloo


    忘了是在哪儿看到的了。我真正完全掌握二叉搜索就是因为理解了循环不变式的概念。其实无论upper-bound还是lower-bound或者精确查询什么的,通过循环不变式可以非常非常简单的解释。

首先,我们规定几个不变式(invariant):
  - 无论如何循环,middle永远在left和right所定义的区间(根据你的定义,也许是[left, right],也许是[left, right)
  - left,right所定义的区间在每次循环中减小。
  - 确保循环会在区间减小到1(或者0——看你的需求)时结束。

其中1是真的invariant,剩下的其实是实现细节。这三点完全保证了算法的正确性,相信并不需要我证明。

所以,对于lower-bound,在满足上述三个条件的时候,添加一个额外条件:如果middle和目标相等,选择左分支,upper反之亦然。而如果只需要匹配,就直接在相等的时候退出。

知道了这些东西以后,二分搜索就极其好写了,甚至并不需要向你那样把边界都列出来——只要满足第一条invariant,边界就一定会满足。

所以,循环不变式是处理迭代问题最有效的方式……

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-07 20:25 |显示全部楼层
回复 66# starwing83

非常非常简单的解释只在你的心里,并没有在你目前写出的文字里。

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-08-07 20:26 |显示全部楼层
回复 67# OwnWaterloo


    ?我的描述有什么问题?难道还不明显了么?

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-07 20:34 |显示全部楼层
回复 68# starwing83

比如:
>>   - 无论如何循环,middle永远在left和right所定义的区间(根据你的定义,也许是[left, right],也许是[left, right)
这是为何?

>>  - left,right所定义的区间在每次循环中减小。
这又是为何?

这些东西都只在你心里,但你没有把原因说出来。
也许是因为原因在你看来是太显而易见了,是不需要思考的直觉反应。但作为论证,这些东西不是一句显而易见就可以带过的。

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-08-07 20:41 |显示全部楼层
回复 69# OwnWaterloo


     不不不,刚好相反,你把因果关系搞反了,也许是我没说明白。

是这样的,所谓循环不变式,是硬性地规定一组契约,保证他们在循环的过程中不变,可以很容易地从这组契约推导出这个算法是正确的,就够了,然后这组契约可以作为实际算法设计的指导思想。invariant是作为证明正确和具体实现之间的“沟通者”的角色存在的。它们是人规定的。

我的意思是,对于二分搜索这个特殊算法,我们可以规定那三个不变式,这是我自己规定的,规定的目的仅仅是为了很容易地看出,满足这三个式子的循环一定能达到我需要的(upper/lower-bound)的目的,这就够了,不需要原因。就像CRC那些magic数字一样。你自己也可以定义自己的一组invariant,只需要这组invariant能方便证明算法正确和指导实现即可。这些invariant并不是循环不变式,循环不变式的思想是“定义invariant”这件事本身。

所以,如果非要说“为什么要这样”,那我只能说,“这么规定能很方便地证明算法正确,也很容易在程序编写的时候,在单个循环里时刻验证,甚至很容易写成assert”,这就是我的回答。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。




----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP