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

OwnWaterloo

回复 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代表私有总该是共识了。
最后，我至于那么傻先去找最右节点吗。。。找出来了能干嘛。。。

OwnWaterloo

yulihua49 发表于 2012-08-04 22:51
习惯问题，一般把有序数组叫二分法，二叉链表叫二叉树，以示方法上的区别，习惯了你的称谓方法，理解上也没问题。
系统的Binary_search(怎么拼写的一时忘了）也是指的对数组的查找。

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

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

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

复制代码

1. 
   
2. multiset<int> s(istream_iterator<int>(cin), (istream_iterator<int>()));
   
3. copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
   

复制代码

我还真不信后者会比前者快。

OwnWaterloo

回复 62# OwnWaterloo

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

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

starwing83

ow你既然降到了二分查找，怎么不讲讲循环不变式在设计二分查找时的应用呢？

OwnWaterloo

回复 64# starwing83

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

starwing83

回复 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，边界就一定会满足。

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

OwnWaterloo

回复 66# starwing83

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

starwing83

回复 67# OwnWaterloo


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

OwnWaterloo

回复 68# starwing83

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

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

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

starwing83

回复 69# OwnWaterloo


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

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

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

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