分治法的几种变形、实例分析、二分查找法 Binary Search

分治法的几种变形
二分法 dichotomy
一种每次将原问题分解为两个子问题的分治法,是一分为二的哲学思想的应用.这种方法很常用,由此法产生了许多经典的算法和数据结构.
分解并在解决之前合并法 divide and marriage before conquest
一种分治法的变形,其特点是将分解出的子问题在解决之前合并.
管道传输分治法 pipelined divide and conquer
一种分治法的变形,它利用某种称为“管道”的数据结构在递归调用结束前将其中的某些结果返回.此方法经常用来减少算法的深度.分治法的实例分析 二分查找法 Binary Search
在对线性表的操作中,经常需要查找某一个元素在线性表中的位置.此问题的输入是待查元素x和线性表L,输出为x在L中的位置或者x不在L中的信息.
比较自然的想法是一个一个地扫描L的所有元素,直到找到x为止.这种方法对于有n个元素的线性表在最坏情况下需要n次比较.一般来说,如果没有其他的附加信息,在有n个元素的线性表中查找一个元素在最坏情况下都需要n次比较.
如果线性表里只有一个元素,则只要比较这个元素和x就可以确定x是否在线性表中.因此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下性质：
比较x和L中任意一个元素L[i],若x=L[i],则x在L中的位置就是i；如果xL[i],同理我们只要在L[i]的后面查找x即可.无论是在L[i]的前面还是后面查找x,其方法都和在L中查找x一样,只不过是线性表的规模缩小了.这就说明了此问题满足分治法的第二个和第三个适用条件.很显然此问题分解出的子问题相互独立,即在L[i]的前面或后面查找x是独立的子问题,因此满足分治法的第四个适用条件.
于是我们得到利用分治法在有序表中查找元素的算法.
function Binary_Search(L,a,b,x);beginif a>b then return(-1)else beginm:=(a+b) div 2;
if x=L[m] then return(m)
else if x>L[m]
then return(Binary_Search(L,m+1,b,x));
else return(Binary_Search(L,a,m-1,x));end;end;在以上算法中,L为排好序的线性表,x为需要查找的元素,b,a分别为x的位置的上下界,即如果x在L中,则x在L[a..b]中.每次我们用L中间的元素L[m]与x比较,从而确定x的位置范围.然后递归地缩小x的范围,直到找到x.
下面分析该算法的复杂性.设在n个元素的数组中查找x需要的比较次数为T(n),如果每次比较x和L[m]时,总有xL[m],即x根本不在L中,则：
该方程的解为T(n)=O(logn).所以在最坏情况下二分查找法的复杂度为O(logn).