分治法的应用

例一：二分查找

例二：计算X的n次幂。

把线性级的时间复杂度降低到了lg级。

#include
//二分查找
int BinSearch(int a[],int begin,int end,int s)
{
int low=begin,high=end,mid=(low+high)/2;

if(a[begin]>s || a[end]
while(low<=high && a[mid]!=s) //注意判定条件的选择
{
if(a[mid]{
low=mid+1;
mid=(low+high)/2;
}
else if (a[mid]>s)
{
high=mid-1;
mid=(low+high)/2;
}
if(low>high)return -1; //找不到返回-1
}
    return mid; //找到，返回所在的下标
}
//计算x的n次幂
int CompXn(int x,int n)
{
if(n==1) return x;
if(n%2==0) return CompXn(x,n/2)*CompXn(x,n/2);//若n是偶数
else return CompXn(x,(n-1)/2)*CompXn(x,(n-1)/2)*x;//若n是奇数
}
int main()
{
int a[10]={1,2,3,4,6,8,9,23,45,678};
int s=23;
//printf("%d  ",BinSearch(a,0,9,s));
int x=3,n=4;
printf("%d  ",CompXn(x,n));
}