算法设计策略-分治法

二分搜索

问题描述

在有序表（已按关键字值非减排序）中搜索给定元素的问题。

分治法求解

设有一个长度为n的有序表(a0,a1,⋯,an−1)，要求在表中搜索与给定元素x有相同关键字值的元素。若n=0，则显然搜索失败；若n>0，则可将有序表分解成若干个子表。最简单的做法是分成两个子表。假定以元素am为划分点，将原表分成(a0,a1,⋯,am−1)和(am+1,am+2,⋯,an−1)两个子表。那么将元素am与给定元素x进行比较，比较结果有三种可能：x<am、x=am和x>am。对于这三种情况，有：

当x<am时，若与x相同关键字值的元素在表中，则必定在子表(a0,a1,⋯,am−1)中，可以在该子表中继续进行搜索；
当x=am时，搜索成功；
当x>am时，若与x相同关键字值的元素在表中，则必定在子表(am+1,am+2,⋯,an−1)中，可以在该子表中继续进行搜索。

根据以上分析，可以得到分治法搜索有序表的算法——二分搜索

//二分搜索算法框架
//后置条件: 在范围为[left,right]的表中搜索与x有相同关键字值的元素；如果存在该元素，则函数返回该元素在表中的位置，否则函数返回－1，表示搜索失败。
template <class T>
  int SortableList<T>::BSearch(const T& x, int left, int right)const
  {
    if(left <= right){
      //按照某种规则求分割点m
      int m = Divide(left, right);
      //使用不同的规则求分割点m，则可得到不同的二分搜索方法，如：对半搜索、斐波那契搜索等。
      if(x<l[m])
        return BSearch(x,left,m-1);
      else if(x>l[m])
        return Bsearch(x,m+1,right);
      else 
        //搜索成功
        return m;
    }
    //搜索失败
    return -1;
  }

对半搜索

对半搜索是一种二分搜索，它的分割点设为m=(left+right)/2。

//对半搜索递归算法
template<class T>
  int SortableList<T>:BSearch(const T& x, int left, int right)const
  {
    //若表（子表）非空
    if(left <= right){
      //对半分割
      int m = (left+right)/2;
      if(x<l[m])
        //搜索左半子表
        return BSearch(x,left,m-1);
      else if(x>l[m])
        //搜索右半子表
        return BSearch(x,m+1,right);
      else 
        //搜索成功
        return m;
    }
    else 
      //搜索失败
      return -1;
  }

对半搜索的正确性用归纳法可以证明。

//对半搜索的迭代算法
template<class T>
  int SortableList<T>::BSearch(T& x)const
  {
    int m, left = 0, right = n-1;
    while(left<=right){
      m=(left+right)/2;
      if(x<l[m])
        right = m-1;
      else if(x>l[m])
        left = m+1;
      else
        //搜索成功
        return m;
    }
    //搜索失败
    return -1;
  }

C语言实验如下：

#include <stdio.h>
//对半搜索递归算法
int BSearch1(int l[], int x, int left, int right)
{
  //若表（子表）非空
  if(left<=right){
      //对半分割
      int m = (left+right)/2;
      if(x<l[m])
        return BSearch1(l, x, left, m);
      else if(x>l[m])
        return BSearch1(l, x, m+1, right);
      else
        return m;
    }
  else
    return -1;
}

//对半搜索的迭代算法
int BSearch2(int l[], int x, int n)
{
  int m, left = 0, right = n-1;
  while(left<=right){
      m = (left+right)/2;
      if(x<l[m]){
          right = m-1;
        }
      else if(x>l[m]){
          left = m+1;
        }
      else
        return m;
    }
  return -1;
}

int main()
{
  int l[5] = {1,2,3,4,5};
  printf("number 5's position is %d
", BSearch1(l, 5, 0, 4));
  printf("number 3's position is %d
", BSearch2(l, 3, 5));
  return 0;
}

实验结果：

number 5's position is 4
number 3's position is 2

二叉判定树

二分搜索过程的算法行为可以用一颗二叉树来描述，通常称这颗描述搜索算法执行过程的二叉树为二叉判定树（binary decision tree）.

一个以关键字值为基础的搜索算法的二叉判定树模型的建立过程：

指定元素x与表中元素l[m]之间的一次比较操作，表现为二叉判定树中的一个内结点（internal node），用一个圆形结点表示，并用m标识。如果x=l[m]，则算法在该结点处成功终止。
二叉判定树的根节点，代表算法中首次与x比较的元素l[m]，用m标识。
当x<l[m]时，算法随后与x比较的元素下标所标识的结点是结点m的左孩子；当x>l[m]时，算法随后与x比较的元素下标所标识的结点是结点m的右孩子。
若x<l[m]且算法终止，那么结点m的左孩子以标号为m-1的方形结点表示；若x>l[m]且算法终止，那么结点m的右孩子以标号m的方形结点表示。方形结点称为外结点（external node）。如果算法在方形结点m处终止，这意味着搜索失败。
从根节点到每一个内结点的一条路径代表成功搜索的一条比较路径。如果搜索成功则算法在内结点处终止，否则在外结点处终止。

二叉判定树性质：

只有n(n>0)个内结点的对半搜索二叉判定树的左子树上有⌊(n−1)/2⌋个内结点，右子树上有⌊n/2⌋个内结点。
具有n(n>0)个内结点的对半搜索二叉判定树的高度为⌊logn⌋+1（不计外结点）。
若n=2h−1，则对半搜索二叉判定树为满二叉树。
若n=2h−2，则对半搜索二叉判定树的外结点均在h+1层，否则，在第h或者h+1层上，h=⌊logn⌋+1。
对半搜索算法成功情况下，关键字之间的比较次数不超过⌊logn⌋+1。失败的情况下，算法需要进行⌊logn⌋或⌊logn⌋+1次比较。
对半搜索算法在搜索成功时的平均时间复杂度为Θ(logn)。

搜索算法的时间下界

定理：在一个有n个元素的集合中，通过关键字值之间的比较，搜索指定关键字值的元素，人以这样的算法在最坏情况下至少需要进行⌊logn⌋+1次比较。

在这个意义上，对半搜索是最优算法。