重新考虑二元搜索(2018)

2020-12-26 00:34:48

有一个更简单的不变代码和一个更简单的代码,它们共同具有一些优点:不利的一面是,即使它在第一次比较中找到了所需的键,它仍然会进行log(size)比较。

该代码的第一个版本(未参考Mike的代码编写)的数组大小为n。那是因为它被更改了,因此不再代表数组的大小,而是代表仍在考虑中的节的大小。我已根据Mike的建议将其更改为n,以使我的日常工作与他的工作更容易进行比较。

因此,这里是我牢记的不变式-与Mike极为相似:请注意,我指定了一个半开区间。 int find(int a [],int size,int val){int lower = 0;如果(size <= 0)返回-1;而(1){if(size == 1)return(val == a [lower])吗?较低:-1; int m =大小/ 2; if(val <a [lower + m])size = m;否则大小-= m,下边+ = m; } return -1; /* 没用过 */ }

当我们进入while循环时,我们知道大小至少为1。测试后,大小至少为2,所以1 <= m <=大小。因此,探测该位置是有效的,并且我们可以看到大小不断减小,因此测试最终成功并且例程返回。我们可以这样检查不变量:在第一种情况下,我们只是通过减小size的值来减小搜索元素的范围。在另一种情况下,我们将下限上移一定量,并将大小减小相同量。所有这些都可以使用明确的上限和下限等效地编写。有人认为这是简单明了的逆行步骤,但却是垫脚石。 int find(int a [],int size,int val){int lower = 0,upper = size;如果(upper&lt; = 0)返回-1; while(1){if(upper-lower == 1)return(val == a [lower])吗?较低:-1; int m =(上下)/ 2; if(val <a [lower + m])upper = m;否则更低= m; } return -1; /* 没用过 */ }

在这里,大小已被适当的代数简化所取代。现在我们可以将return语句移到while循环之外:int find(int a [],int size,int val){if(size&lt; = 0)return -1; int lower = 0,upper = size; while(upper-lower&gt; 1){int m = lower +(upper-lower)/ 2; if(val <a [m])upper = m;否则更低= m;返回(val == a [lower])?较低:-1; }

简短的观点-有时我们需要使代码更混乱,以便于进行比原始代码更清晰的重写。这也许有点像从局部最大的山坡上爬下来,所以我们可以到达山谷另一侧的更高(可能最高)的最大值。

这个版本更短更干净。不变量说,i-如果存在,则处于半开区间[lower,upper]。这意味着它可以是[lower,m)或[m,upper),并且代码只是选择了正确的代码。还有其他要检查的事情。该算法永远不会溢出,并且我们绝不会在参数保证存在的边界之外访问数组。 size的值(或其等效的upper-lower)严格减小且为正值,因此该循环在达到1时终止。它看起来很防弹。 (著名的遗言)请注意,无论使用哪种语言变量,我都不必担心变量的符号性或可能的溢出条件,因为代码的结构确保了我永远不会超出传入值所保证的范围。因此,让我们考虑一下这与博客文章中的版本之间的区别。一个区别是,它永远不会尽早终止。 Italways始终执行log(n)步骤,并且如果有equalkeys,则始终返回最后一个。这是一个有趣的行为变化,应引起注意。它可以使时间行为保持一致,但是这意味着,如果您碰巧很早就猜中了,就不会很快得到结果。但是看一下代码,我们可以发现我们没有将边界范围(Lower和Lower + n)设置在潜在的允许探针位置之外。迈克(Mike)的密码集降低到i + 1,您可能需要担心它是否溢出。这一切都相当蓬松。也许值得扩展,但是我不愿意陷入围绕该问题经常爆发的火焰战争。

实际上并没有,但是更容易推断出在潜在溢出条件下第二例程的正确性。 特别是,要对迈克的例程为什么没有上溢或下溢问题进行推理,需要对所使用的C的特定风味进行推理。 我的感觉是,这某种程度上意味着推理更加“脆弱”。 在某种意义上。 我自由地同意,有时知道这些事情是至关重要的,但是如果可以避免,那么它将带来一个自己的控制问题,否则这些问题将被推到实现上。 但是,这些都不是结论性的。 更简单吗? 就个人而言,我发现从此不变式进行的详细推理比在Mike的情况下容易,但也许这只是选择偏见。 毕竟,我编写了这段代码,而迈克则编写了他的代码,所以也许该代码反映了我们各自的思维方式。