【参考答案】论1.5 分析“二分法”

<p><code class="brush:cpp;toolbar:false" >/*&nbsp;讨论1.5&nbsp;分析“二分法”&nbsp;*/ //首先，递归的伪码最贴近二分法的定义： Position&nbsp;Binary_Search(&nbsp;ElementType&nbsp;List[],&nbsp;ElementType&nbsp;X,&nbsp;Position&nbsp;Left,&nbsp;Position&nbsp;Right&nbsp;) { if&nbsp;(left&nbsp;&lt;=&nbsp;Right)&nbsp;{&nbsp;/*&nbsp;如果搜索范围中还有数据&nbsp;*/ /*&nbsp;先找到序列的中点&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;Position&nbsp;M&nbsp;=&nbsp;(Left&nbsp;+&nbsp;Right)&nbsp;/&nbsp;2; /*&nbsp;将List[M]与X进行比较*/ if&nbsp;(List[M]&nbsp;==&nbsp;X)&nbsp;&nbsp;return&nbsp;M;&nbsp;/*&nbsp;若相等则返回中点下标&nbsp;*/ else&nbsp;/*&nbsp;否则&nbsp;*/ /*&nbsp;若List[M]&gt;X，则在左边的子系列中查找&nbsp;*/ if&nbsp;(List[M]&nbsp;&gt;&nbsp;X)&nbsp;Binary_Search(List,&nbsp;X,&nbsp;Left,&nbsp;M-1); /*&nbsp;若List[M]&lt;X，则在右边的子系列中查找&nbsp;*/ else&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Binary_Search(List,&nbsp;X,&nbsp;M+1,&nbsp;Right); } &nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;return&nbsp;-1;&nbsp;/*&nbsp;否则返回-1表示没有找到&nbsp;*/ } /* 先看空间： 由于List是作为指针参数传递的，所以原始序列List在函数运行中占用的空间是个常数。 每次调用函数的时候要声明一个M，一系列递归就要声明一系列M，所以这个M占用的空间跟递归的次数 成正比。 总之空间复杂度取决于递归调用的深度： 最好情况是1次就找到，复杂度是O(1)； 最坏情况是根本找不到——由于我们每次递归都把搜索范围缩小一半，也就是N/2/2/2...直到得到1，于是 有公式N/2^k=1，推出k=log_2&nbsp;N，即递归最多需要O(logN)次，占用的空间跟递归的次数成正比，也就是O(logN)。 再看时间： 最好情况下，1次就找到，当然用的时间是O(1)； 注意到每次调用函数时，除了需要继续递归之外，其他操作都是if-else判断，只用 常数级O(1)的时间完成，于是我们有：T(N)&nbsp;=&nbsp;T(N/2)+O(1)&nbsp;——注意这里不是2T(N/2)，因为我们每次只选1边 进行递归，不是2边都要找。显然可以递推：T(N/2)&nbsp;=&nbsp;T(N/2/2)+O(1)，T(N/2/2)&nbsp;=&nbsp;T(N/2/2/2)+O(1)，…… 最坏情况下我们必须递归到底，即一直进行到T(N/2^k)&nbsp;=&nbsp;T(1)+O(1)。把这些式子一层层代进最初的式子： T(N)&nbsp;=&nbsp;T(N/2)+O(1)&nbsp;=&nbsp;T(N/2/2)+2*O(1)&nbsp;=&nbsp;T(N/2/2/2)+3*O(1)&nbsp;=&nbsp;...&nbsp;=&nbsp;T(1)+k*O(1)，而k=log_2&nbsp;N，T(1)=O(1)， 所以得到T(N)=O(logN)。 注意：不是说递归logN层就一定会得到O(logN)的时间复杂度哦！不信看看算法3…… */ //当然，任何递归代码都可以转换为循环代码，运行起来效率更高，特别是空间复杂度方面。二分法的循环版本如下： Position&nbsp;Binary_Search(&nbsp;ElementType&nbsp;X,&nbsp;ElementType&nbsp;List[],&nbsp;int&nbsp;N&nbsp;) { Position&nbsp;Left,&nbsp;Right,&nbsp;M; Left&nbsp;=&nbsp;0;&nbsp;Right&nbsp;=&nbsp;N-1; while&nbsp;(Left&nbsp;&lt;=&nbsp;Right)&nbsp;{ Position&nbsp;M&nbsp;=&nbsp;(Left&nbsp;+&nbsp;Right)&nbsp;/&nbsp;2; if&nbsp;(List[M]&nbsp;==&nbsp;X)&nbsp;&nbsp;return&nbsp;M; else&nbsp; if&nbsp;(List[M]&nbsp;&gt;&nbsp;X)&nbsp;&nbsp;Right&nbsp;=&nbsp;M-1; else&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Left&nbsp;=&nbsp;M+1; } return&nbsp;-1; } /* 这个版本与递归版本的区别，就是空间复杂度始终是O(1)。 虽然最坏时间复杂度的理论分析是一样的（因为满足Left&lt;=Right&nbsp;的次数跟递归深度是一样的）， 但是在实际执行过程中，由于不用递归存储、释放log_2&nbsp;N个函数的状态，还是略快一些的。 */ /* 话说，对于想用二分法的用户来说，循环版的接口比较好理解：从N个元素的List[]中找X。但是 递归版的接口就不那么友好了，用户很可能不明白Left和Right是什么鬼……&nbsp;如果要求你把递归版 的接口也改成跟循环版一样，该怎么办呢？ */</code></p>