折半算法示例集锦
例1：计算x的N次方(N>=0)。

常规算法，复杂度为O(N):
double Power(double x, unsigned int N)
{
 double result = 1.0;
 for (unsigned int i=0; i<N; i++)
  result *= x;
 return result;
}

折半算法，复杂度为O(logN):
double Power(double x, unsigned int N)
{
 if (N == 0)
  return 1.0;
  
 double t = Power(x, N/2);
 if (N % 2 == 0)
  return t * t;
 else
  return t * t * x;
}

例2：静态查找问题，给定一个整数x和一个数组a，返回x在a中的下标，或者返回x不存在的标志。
如果x不止出现一次，则返回其中任意一个。
 若数组a未经过排序，则我们只能对数组进行线性顺序查找，复杂度为O(N):
template <typename T>
int OrderSearch(const vector<T> & a, const T & x)
{
 for (int i=a.size()-1; i>=0; i++)
 {
  if (a[i] == x)
   return i;
 }
 
 return NOT_FOUND; //NOT_FOUND = -1;
}
 若数组a已经经过排序，则我们可以使用折半查找，复杂度为O(logN):
template <typename T>
int OrderSearch(const vector<T> & a, const T & x)
{
 int low = 0;
 int high = a.size() - 1;
 int mid;
 
 while (low <= high)
 {
  mid = (low + high) / 2;
  
  if (a[mid] == x)
   return mid;
   
  if (a[mid] < x) //若a[mid] < x，则x位于 mid+1 ~ high 之间
   low = mid + 1;
  else //若a[mid] > x，则x位于 low ~ mid-1 之间
   high = mid - 1;   
 }
 
 return NOT_FOUND; //NOT_FOUND = -1;
}  
 如果希望折半查找的速度更快一些，那么我们需要让内部循环变得更紧凑一些。一种可能的
策略是去除成功查找的内部循环中的测试，并且在所有情况下都把范围缩小为一项。最后我们可以
使用循环外的单个测试来确定是否能找到该项。
template <typename T>
int OrderSearch(const vector<T> & a, const T & x)
{
 int low = 0;
 int high = a.size() - 1;
 int mid;
 
 while (low <= high)
 {
  mid = (low + high) / 2;
  
  if (a[mid] < x) //若a[mid] < x，则x位于 mid+1 ~ high 之间
   low = mid + 1;
  else
   high = mid
 }
 
 return (low == high && a[low] == x) ? low : NOT_FOUND; //NOT_FOUND = -1;
}

评论