学步园

例一：二分查找

例二：计算X的n次幂。

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

#include<stdio.h>
//二分查找
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]<s) return -1;

	while(low<=high && a[mid]!=s) //注意判定条件的选择
	{
		if(a[mid]<s)
		{
			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));
}