折半算法示例集锦例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;}

评论