＞第 11 章 排序与查找＞折半查找＞习题

第2题：
double mysqrt(double y)
{
	double low,high,x;	//here x is the same as middle;
	low=0.0,high=y;
	x=(low+high)/2;
	while(low <= high && !(abs(x*x - y) <= 0.001)){
		if(x*x - y > 0){	//x is larger than supposed;
			high=x;
			x=(low+high)/2;
		}else if(x*x - y < 0){	////x is smaller than supposed;
			low=x;
			x=(low+high)/2;
		}
		else
			break;
	}
	return x;
}

不好意思，上面的代码测试有个问题；可能是abs()精度不够，修改如下就可以了。
double mysqrt(double y)
{
	double low,high,x;	//here x is the same as middle;
	low=0.0,high=y;
	x=(low+high)/2;
	while(low <= high && !(x*x - y <= 0.001 && x*x - y >= -0.000001)){
		if(x*x - y > 0)	//x is larger than supposed;
			high=x;
		else if(x*x - y < 0)	////x is smaller than supposed;
			low=x;
		else
			break;
		x=(low+high)/2;
	}
	return x;
}

第3题：
思想是把n换成2进制，5=101=1*1+10*0+100*1=1+0+4,
则x的n次方=x^(1+0+4)=x^1 * X^4 ,略过0位就可以了；程序如下：
double mypow(double x, int n)
{
	int bin[128],i,max;
	double pow,prepow;

	for(i=0;n>=1;++i){	//convert n to binary;
		bin[i]=n%2;
		n=n/2;
	}
	max=--i;

	pow=1.0,prepow=x;
	for(i=0;i<=max;++i){
		(bin[i]==1)?(pow=pow*prepow):0;
		prepow=prepow*prepow;
	}

	return pow;
}

递归版：

#include <stdio.h>

double mypow(double x, int n)
{
        if (n)
                if (n % 2 == 0)
                        return mypow(x, n/2) * mypow(x, n/2);
                else
                        return x * mypow(x, n-1);
        else
                return 1;
}

int main(void)
{
        printf("%f\n", mypow(2, 4));
        return 0;
}

循环版：

#include <stdio.h>

double mypow(double x, int n)
{
        int i = 1, temp = n;
        double product = x; 

        if (n % 2 != 0)
                temp = n - 1;
        while (i < temp) {
                product = product * product;
                i *=  2;
        }
        if (temp == n - 1)
                product *= x;
        
        return product;
}

int main(void)
{
        printf("%f\n", mypow(2, 5));
        return 0;
}

例 11.5. 带有测试代码的折半查找
int mustbe(int start, int end, int number)
这个函数不很矛盾吗？本来是折半的，又搞个遍历？查错不能这样处理吧。

如果您有建设性意见，哪怕只是纠正一个错别字，也请不吝赐教，您留下的姓名和email将会出现在本书前言的致谢中。再次感谢您的宝贵意见！