菜鸟天堂

本文是《数据结构与程序设计（c++语言描述）》中关于二分搜索的学习笔记，二分搜索的思想很简单，但是要实现一个正确最优的算法确不是那么容易。第一个二分搜索算法于1946年就出现，然而第一个完全正确的二分搜索算法直到1962年才出现，所以，认真点＋留神点～ ^_^

首先，介绍一下二分搜索的思想：对于一个有序表而言，要查找某个关键字，首先比较表中央的那个节点，如果该节点的关键字与目标关键字相同，则找到。若比目标小，则目标关键字肯定出现在该点的右半段内。反之则出现在左半段。这样，每次比较后就能丢去一半的节点，对于一般的有序线性表而言，其搜索效率大大高于顺序查找。

第一个版本的二分搜索：
根据算法，我们设置三个位置指示器：low, high, mid，分别指向当前搜索范围的最低位置、最高位置和中间位置，中间位置由mid = (low+high)/2决定。首先将mid处的关键字与key比较，相同则返回mid；若key较大，令low＝mid＋1继续搜索右半段；若key较小，令high＝mid－1继续搜索左半段。这样，搜索范围不断减小，high－low也越来越小。当high-low<0时算法由于没有找到key而终止。

///////////////////////////////////程序实现///////////////////////////////////////////
//第一个版本的递归实现（binary_search_v1_recursion）
template<class Record, class Key>
int binary_search( Record * r, const int & low, const int & high, const Key & k )
{
 int mid = ( low + high ) / 2;
 if( low <= high )
 {
  if( r[mid] == k )
   return mid;
  else if( r[mid] < k )
   return binary_search( r, mid+1, high, k );
  else
   return binary_search( r, low, mid-1, k );
 }
 else
  return -1;
}

//第一个版本的迭代实现（binary_search_v1_iteration）
template<class Record, class Key>
int binary_search( Record * r, const int & size, const Key & k )
{
 int low=0, high=size-1, mid;
 while( low <= high )
 {
  mid = (low + high)/2;
  if( r[mid] == k )
   return mid;
  else if( r[mid] < k )
   low = mid + 1;
  else
   high = mid -1;
 }
 return -1;
}

在这个版本中，由于>，<符号的使用，搜索的范围始终控制在[low, high]之间，在0～low－1之间的一定小于关键字，在high＋1～size－1之间的一定大于关键字。当找到一个关键字时退出循环算法结束（成功）。考虑一下如果一张有序表中有多个重复关键字怎么办呢？一般的习惯是返回第一个的序号，然而此版本的算法只是返回随机的一个位置。这是一个问题。

///////////////////////////////////复杂度分析///////////////////////////////////////////
接下来分析一下和目标关键字k的比较次数。在分析用关键字比较次数来作为算法时间复杂性度量的这一类查找算法时，比较树（comparison tree）是很有用的一种方法。在此介绍两种类型的比较树（当然是和算法有关），它们都符合2－树的定义。所谓2－树就是树中的节点要么是叶子节点要么有两个儿子节点（注意：2－树不是二叉树，前者的条件更强些）。二叉树相信大家已经非常熟悉了，所以这里直接拿出它的两个引理而不加证明：
1）第i层上最多有2^i个节点（0<=i<<h=树深度）。
2）高度为h的一棵二叉树最多有（2^h）-1个节点，节点最多时为满二叉树。

易验证这里的比较树都是2－树，而2－树是条件更强的二叉树，自然满足1）、2）。
此算法的的比较树如下（size＝10）：

在这棵查找树中，内部节点（i）表示一次查找成功，外部（叶子F）节点表示一次查找失败，形象一点的话可以说查找成功的情况分布在树冠（树的上部）查找失败的情况树的底层或次底层（可用数学归纳法证明，从略啦）。在证明过程中需要特别注意的是若是查找成功，成功节点的祖先（在比较路径上从root（第0层）到成功节点的父亲）各比较了两次！而成功节点自身则比较了一次。失败的话自然路径上的每个内部节点都比较了两次。另外注意内部节点有n个，外部节点有n＋1个（n表示有序表大小）。

查找失败：
查找失败时的比较次数与树的深度密切相关。假设深度h，则F节点分布在h层或h和h－1层。由于h－1层上非F节点都会在h层产生两个F节点，因此：2^(h-1) < n+1 <= 2^h 。所以树深度h= ┌lg(n+1)┐（以2为底）。所以平均情况和最坏情况下查找失败的比较次数是2×┌lg(n+1)┐。

查找成功：
首先引入2－树的引理：对于任何一个2－树而言（二叉树就没有这个定理！），外部路径总长度E＝内部路径总长度I＋内部节点个数q×2。可以用数学归纳法证明，不是很难，从略。E≈(n+1)┌lg(n+1)┐ ∴I＝(n+1)┌lg(n+1)┐－2n 。平均内部路径长度＋1表示平均比较的节点数，故:
（I/n＋1）×2－1＝2（n＋1）┌lg(n+1)┐/n－3就是成功查找的平均查找长度。其中×2表示每个节点都比较2次（除了最后一个节点），最后的减1也就是减去那个多算的1次比较。
另外一种求法是从上到下计算每一层的比较次数然后相加，这是国内很多教材选用的方法，比较直接且麻烦，偶不喜欢～。
查找成功时的最坏情况当然是树的深度减1：┌lg(n+1)┐－1 。

第一个版本的二分搜索：
前面一个版本二分搜索特点是当找到一个成功情况时就退出，这样对于具有多个相同关键字的有序表来说就不太适合了，最好返回这些相同关键字的第一个的位置而不是随便一个。由此引出了下面的改进算法：当mid处的关键字等于k时，算法并不马上结束，因为mid之前可能还有相同的关键字，也就是说第一个关键字的位置<=mid，所以令high=mid。那么这个算法结束的条件是什么呢？这个是关键。当low或high中的任何一个先指向第一个k关键字时，在接下来的迭代过程中该指针将保持不变，另一个指针会不断向它靠近直到high＝low。也就是说high＝low是查找成功的必要条件，可见：（high＝low）&&（mid处关键字＝k）就是查找成功的充分条件。查找失败有两种可能：
1）（high＝low））&&（mid处关键字≠k）
2）low > high

///////////////////////////////////程序实现///////////////////////////////////////////
//第二个版本的递归实现（binary_search_v2_recursion）
template<class Record, class Key>
int binary_search( Record * r, const int & low, const int & high, const Key & k )
{
 int mid = (low + high)/2;
 if( low < high )
 {
  if( k <= r[mid] )
   binary_search( r, low, mid, k );  
  else
   binary_search( r, mid+1, high, k );
 }
 else if( low == high )
 {
  if( k == r[mid] )
   return low;
  else
   return -1;
 }
 else
  return -1;
}

//第二个版本的迭代实现（binary_search_v2_iteration）
template<typename Record, typename Key>
int binary_search( Record * r, const int & size, const Key & k )
{
 int low=0, high=size-1, mid;
 while( low < high )
 {
  mid = (low + high) / 2;
  if( k > r[mid] )
   low = mid + 1;
  else
   high = mid;
 }
 if( low > high )
  return -1;
 else
 {
  if( k == r[low] )
   return low;
  else
   return -1;
 }
}

///////////////////////////////////复杂度分析///////////////////////////////////////////
由于成功和失败的判断一定要走到最后一步才能确定，所以成功和失败的情况都是在2－树的叶子（外部）节点反之亦然。而这些外部节点总数为2n（n为有序表大小），所以比较树的深度h＝┌lg(2n）┐＝┌lgn┐＋1 。由于2－树叶子节点层数最多相差1，所以查找成功/查找失败时的平均比较次数和最坏比较次数均≈┌lgn┐＋1 。算法2的比较树如下（n＝10）：

由此得出结论，虽然算法1和算法2的时间复杂度是一个级别，但是当n较大时，算法2要比算法1快1倍！虽然从表面看算法1在某些情况下（树顶的那些成功节点）的确比算法2先结束，但是它只是对处于搜索树上部的一些为数不多的节点来说是早结束，而付出的代价却是每个节点比较2次。n较小的时候可能算法1稍微快点，但是此时的n非常小（比较对数曲线）以至于采用顺序查找会比二分算法1更好。由此我们得出结论如下：
对于较大的有序表，采用二分搜索算法2最快。
对于较小的有序表，采用顺序搜索就可以啦。

当然了，实际上由于算法1的两次比较都是相同两个数之间的比较，所以对于某些优化的编译器来说，可能实际的比较时间比两次独立的比较所需的时间要少（比如重复访问的数据直接从cache而不是从ram中读。。。etc）。

呵呵，写到这里终于结束啦。各位各位，如果将来面试的时候考官叫你写个二分搜索算法，你会写哪个呀？要想起我哦，呵呵～