1、本节的折半查找算法有一个特点：如果待查找的元素在数组中有多个则返回其中任意一个，以本节定义的数组int a[8] = { 1, 2, 2, 2, 5, 6, 8, 9 };为例，如果调用binarysearch(2)则返回3，即a[3]，而有些场合下要求这样的查找返回a[1]，也就是说，如果待查找的元素在数组中有多个则返回第一个。请修改折半查找算法实现这一特性。

//By LYLtim#include
     
      #define LEN 8int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };int Search(int k){	int start = 0, end = LEN -1;	while (start <= end) {		int mid = (start + end) >> 1;		if (k < a[mid])		    end = mid -1;		else if (k > a[mid])		    start = mid +1;		else {			while (a[mid-1] == a[mid]) mid -= 1;			return mid;		}	}	return -1;}		int main(void){	printf("%d\n",Search(2));	return 0;}
     

 

2、编写一个函数double mysqrt(double y);求y的正平方根，参数y是正实数。我们用折半查找来找这个平方根，在从0到y之间必定有一个取值是y的平方根，如果我们查找的数x比y的平方根小，则x²<y，如果我们查找的数x比y的平方根大，则x²>y，我们可以据此缩小查找范围，当我们查找的数足够准确时（比如满足|x²-y|<0.001），就可以认为找到了y的平方根。

//By LYLtimdouble mysqrt(double y){	double l = 0, r = y, x;	while (r - l > 0.000001) {		x = (l + r) / 2;		if (x * x > y) r = x;		else l = x;	}	return (l + r) / 2;}

 

3、编写一个函数double mypow(double x, int n);求x的n次方，参数n是正整数。最简单的算法是：

double product = 1;for (i = 0; i < n; i++)	product *= x;

这个算法的时间复杂度是Θ(n)。其实有更好的办法，比如mypow(x, 8)，第一次循环算出x·x=x²，第二次循环算出x²·x²=x⁴，第三次循环算出⁴·x⁴=x⁸。这样只需要三次循环，时间复杂度是Θ(lgn)。思考一下如果n不是2的整数次幂应该怎么处理。

1 // 递归版 By LYLtim 2 double mypow(double x, int n) 3 { 4     if (n == 1) return x; 5     else { 6         double tmp = mypow(x, n >> 1); 7         tmp *= tmp; 8         if (n & 1) 9             return tmp * x;10         else11             return tmp;12     }13 }

1 // 非递归版 By LYLtim  2 double mypow(double x, int n){ 3     double s = 1; 4     while (n) { 5         if (n & 1) s *= x; 6         x *= x; 7         n >>= 1; 8     } 9     return s;10 }