分治法的适用条件及基本步骤，快速幂算法
分治法所能解决的问题一般具有一下几个特征
*该问题的规模缩小到一定程度就可以容易的解决
*该问题可以分解为若干个规模较小的问题
*利用该问题分解的子问题的解可以合并为该问题的解
*该问题所分解出的各个子问题是相互独立的
divide-and-conquer(P){
if(|p| <= n0) adhoc(P); 解决小规模的问题
divide P into smaller subinstances P1,P2,....Pk //分解问题
for (i=1,i<=k,i++)
yi=divide-and-conquer(Pi); //递归的解的各个子问题
return merge(y1,......yk); //各子问题的解合并为原问题的解
复杂性分析：
分治法将规模为n的问题分成k个规模为n/m的子问题去解
（1）设分解阈值n=1且adhoc解规模为1的问题耗费1个单位时间
（2）设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需要f(n)个单位时间。
（3）用T(n)表示分治法解规模为|P|=n的为题所需的计算时间
T(n) = O(1) n=1
T(n) = kT(n/m) + f(n) n>1
二分搜索技术
非递减序的n个元素a[0:n-1],先要在这n个元素中找出一特定的元素x
分析：设在a[l:r]中找x，mid=（l+r）/2
（0）如果x==a[mid]，则找到
（1）如果x<a[mid]，则继续在a[i,mid-1]中找x即可
（2）如果x>a[mid]，则继续在a[mid+1,j]中找x即可
递归算法：
template<class Type> //递归
int BiSearch(Type a[], const Type& x, int l, int r)
{
if (r > l)
{
int m = (l + r) / 2;
if (x == a[m])
return m;
else if (x < a[m])
return BiSearch(a, x, l, m - 1);
else
return BiSearch(a, x, m + 1, r);
}
else return -1;
}非递归算法：
template<class Type> //非递归
int BiSearch(Type a[], const Type& x, int l, int r)
{
while (r >= l)
{
int m = (l + r) / 2;
if (x == a[m])
return m;
if (x < a[m])
r = m - 1;
else l = m + 1;
}
else return -1;
}非递归算法复杂度分析：每执行一次while循环，带搜索数组的大小减少1/2，在最坏的情况下，while循环被执行了O(logn)次，因此算法在最坏的情况下的计算时间复杂性为O(logn).
快速幂算法：
给定实数a和非负整数n，用分治法设计求a^n的快速算法（递归算法）
分析：
a^n = 0 a=0
a^n = 1 n=0
a^n = (a^(n/2))^2 n > 0,n为偶数
（a^(n/2)^2 * a n > 0,n为奇数
double exp2(double a, int n)
{
if (a == 0)
return 0;
if (n <= 0)
return 1;
else
{
int x = exp2(a, n / 2);
if (n % 2)
return a * x * x;
else
return x * x;
}
}给定正整数a和n，用二分法设计出求a^n的快速算法（非递归算法）
举例求a^93
n=93的二进制表示（如图）
0 1 0 1 1 1 0 1
a^128 a^64 a^32 a^16 a^8 a^4 a^2 a
因此：a^93--------->a^64*a^16*a^8*a^4*a
double exp2(double a, int n)
{
int i;
double b, s = 1.0;
i = n;
b = a;
while (i > 0)
{
if (i % 2)
s *= b;
i /= 2;
b *= b;
}
return s;
}