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

hbmhalley

这他喵的也能吵起来，三行代码能争出个毛，找个算导里证了两页纸以上的算法来吵，要是还吵不出个所以然，就说明这个问题O疼

OwnWaterloo

回复 81# hbmhalley

那首先统一术语就够开几楼了。

starwing83

回复 80# OwnWaterloo


    如果每样都得在原地证明那算法导论估计有100米厚了，很显然就是很显然，不能因为担心某些人看不出来而不显然，要知道弱智总是有的…

hbmhalley

回复 82# OwnWaterloo


    1. 那个循环不变式的正确性不显然么？1) 一定会终止 2) 如果终止，一定是答案 --> 算法正确。

    2. 周长一定为什么圆的面积最大这我还真想知道 .. 需要看什么书?

OwnWaterloo

回复 83# starwing83

这楼本来就是为了将这东西说清楚，又不是算法导论。
即使是算法导论，会像66楼那样偷工减料？反正对作者来说这很明显，所以任何逻辑推理都不需要了，如果看不懂就是读者弱智了？

OwnWaterloo

hbmhalley 发表于 2012-08-09 01:37
1. 那个循环不变式的正确性不显然么？1) 一定会终止 2) 如果终止，一定是答案 --> 算法正确。

如果满足那几个条件，那算法就正确。如果...那，这里的逻辑关系是显然的。
但这个前提本身呢？如何说明算法是满足那几个条件的呢？我不觉得这是显然的。


先看66楼：

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

我第一反应认为这句话是在说"解释整个算法是非常非常简单"，而不是"如果...那"是非常非常简单的，不算误解吧？
然后再对比75楼，真的好意思说非常非常简单么？

hbmhalley 发表于 2012-08-09 01:37
2. 周长一定为什么圆的面积最大这我还真想知道 .. 需要看什么书?

这我也不知道，只是作为例子而已。
显而易见的结果用是可以用。但要论证的话就不能显而易见一句话带过。

starwing83

回复 86# OwnWaterloo


    1. 75楼比你一楼的说明短。
2. 75楼主要解释那个如果就，说明算法符合条件的只有几个注释和一段描述，你说短不短？

OwnWaterloo

回复 87# starwing83

我从一开始在意的就不是你所说的非常非常简单的解释会比我的短。
而是你所说的非常非常简单的解释，其实是包含了类似"等周长圆面积最大"这种显而易见的结论。但它们只是直觉反应，而不是解释。

再说，我在1楼可是说了很多废话的，还用ascii字符画了图的。
如果像你那样的标准，我同样可以只给出函数的含义，并且用这个含义去实现函数本身，再配几个注释 —— 其他的就是显而易见了，看不懂就是读者弱智了。
但我一开始的目的就不是为了追求短。真要追求短，撂下一句"显而易见、你懂的" —— 对我来说就是这样 —— 就完了，我何必去废功夫解释？

OwnWaterloo

回复 87# starwing83

也就是说，和我比短？能不能短出一个数量级？
例如两人相向行走、一只苍蝇在他们之间往返飞，已知3者的速度以及两人的初始距离，求相遇时苍蝇总共走多远。
一人用较通用的微积分，而另一人注意到苍蝇不断在飞这个事实直接用时间x速度，这就就是复杂程度完全不同的两种解释。（微积分更通用不是这个例子的重点）
显然 —— 我可以说显然吗？ —— 没有。两者递归与循环不变式之间的对应关系我前面已经说了，一句话，就是functional与imperative的区别。


在这种数量级等同的情况下，剩下的只是叙述方式不同而已。
你说你的短，我还可以说你的不够清楚呢。
比如重要的地方我还画了图。在你看来这是不是完全疯了？这么显而易见的事？但我觉得有必要，因为我目的就不是只追求短。

类似if (p)与if (p!=0)那样，风格(style)问题而已。
在这里我选择if (p!=0)以避免不清楚if (exp)实际是if (exp!=0)的人有误会。
要平时，我也会直接写if (p)。没必要在这里刻意去追求短。

你想批评我不该选择这么verbose的方式？这也太愤青了。。。
为了向他人介绍某些事实而写的demo代码，会比平时仅为自己完成什么功能写的代码更verbose，这是很正常的事情。
为了向他人说明而写的文字，比自己在大脑里的思考更verbose，也是很正常的事。


另外，如果你想比短。可以和自己比。比如66楼与75楼。
并体会66楼到底缺了什么，以及我一开始到底是想吐槽什么。
并体会我一开始到底是在吐槽什么。

hbmhalley

OwnWaterloo 发表于 2012-08-09 01:47
如果满足那几个条件，那算法就正确。如果...那，这里的逻辑关系是显然的。
但这个前提本身呢？如何说明算法是满足那几个条件的呢？我不觉得这是显然的。

“如果.. 那..”的条件只有一个，就是“算法会终止”。你是指这个不够显然么？

由于始终保证 right-left>=0，且 只要right-left>0，则每次迭代会使 right-left 减小，且right-left==0时结束。

还是显然啊，就是整数长度“越来越短所以会停”而已。

“如果..那..”的推论也差不多啊，一开始答案在[left,right)里，每次排除掉的一定不是答案，因而结果一定还在[left,right)里。如果停了，那么候选集合里只剩一个元素(我不清楚你们说的是停在[i,i+1)上还是[i,i)，不过没关系 差不多)，显然肯定是答案。