分治算法

b

<H2>其他资料</H2><>请参阅以下文章：</P><UL><LI><a href="http://algorithm.myrice.com/algorithm/technique/recursion/index.htm" target="_blank" >递归技术</A> <LI><a href="http://algorithm.myrice.com/algorithm/technique/greedy/index.htm" target="_blank" >贪心法</A> <LI><a href="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/index.htm" target="_blank" >动态规划</A> <LI><a href="http://algorithm.myrice.com/problems/index.html?by_strategy/divide_and_conquer.htm" target="_blank" >分治法问题集</A></LI></UL>

b

<H2>二分查找法 Binary Search</H2><>在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。</P><>比较自然的想法是一个一个地扫描L的所有元素，直到找到x为止。这种方法对于有n个元素的线性表在最坏情况下需要n次比较。一般来说，如果没有其他的附加信息，在有n个元素的线性表中查找一个元素在最坏情况下都需要n次比较。</P><>下面我们考虑一种简单的情况。假设该线性表已经排好序了，不妨设它按照主键的递增顺序排列（即由小到大排列）。在这种情况下，我们是否有改进查找效率的可能呢？</P><P>如果线性表里只有一个元素，则只要比较这个元素和x就可以确定x是否在线性表中。因此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下性质：</P><P>比较x和L中任意一个元素L，若x=L，则x在L中的位置就是i；如果x&lt;L，由于L是递增排序的，因此假如x在L中的话，x必然排在L的前面，所以我们只要在L的前面查找x即可；如果x&gt;L，同理我们只要在L的后面查找x即可。无论是在L的前面还是后面查找x，其方法都和在L中查找x一样，只不过是线性表的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。很显然此问题分解出的子问题相互独立，即在L的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。</P><P>于是我们得到利用分治法在有序表中查找元素的算法。</P>

b

<RE>function Binary_Search(L,a,b,x);
begin
if a&gt;b then return(-1)
            else begin
                   m:=(a+b) div 2
                   if x=L[m] then return(m)
                             else if x&gt;L[m]
                                    then return(Binary_Search(L,m+1,b,x))
                                    else return(Binary_Search(L,a,m-1,x));
                  end;
end;</PRE>

b

<>在以上算法中，L为排好序的线性表，x为需要查找的元素，b,a分别为x的位置的上下界，即如果x在L中，则x在L[a..b]中。每次我们用L中间的元素L[m]与x比较，从而确定x的位置范围。然后递归地缩小x的范围，直到找到x。</P>
<>下面分析该算法的复杂性。设在n个元素的数组中查找x需要的比较次数为T(n)，如果每次比较x和L[m]时，总有x&lt;&gt;L[m]，即x根本不在L中，则：</P>
<BLOCKQUOTE>
<>T(n)=2+T(n/2),T(1)=1</P></BLOCKQUOTE>
<P>该方程的解为T(n)=O(logn)。所以在最坏情况下二分查找法的复杂度为O(logn)。</P>

coby

<>请问楼主</P><>您的这些资料 有没有 具体的来源啊</P><>如果有比较好的查找这方面的网址 可否一并分享啊</P><P>感激不尽 或者pm偶啊</P>[em07]

coeeoc

谢谢

lwd1981

好啊！