算法--二分查找--求平方根（循環法/遞歸法）

二分查找：

1. 資料需要是順序表（數組）
2. 資料必須有序
3. 可以一次排序，多次查找；如果資料頻繁插入，删除操作，就必須保證每次操作後有序，或者查找前繼續排序，這樣成本高，二分查找不合适
4. 資料太小，不用二分查找，直接周遊
5. 資料太大，也不用，因為數組需要連續的記憶體，存儲資料比較吃力
6. 複雜度 lg2n

題目： 求一個數的平方根

• 例如：二分法求根号5

  a:折半： 5/2=2.5

  b:平方校驗： 2.5*2.5=6.25>5，并且得到目前上限2.5

  c:再次向下折半：2.5/2=1.25

  d:平方校驗：1.25*1.25=1.5625<5,得到目前下限1.25

  e:再次折半：2.5-(2.5-1.25)/2=1.875

  f:平方校驗：1.875*1.875=3.515625<5,得到目前下限1.875

循環求解：

#include<iostream>
double rootbinarysearch(double num)
{

	if(num == 1)
		return 1;
	double lower = 1, upper = num, curValue;
    if(lower > upper)
        std::swap(lower,upper);
	while(upper-lower > 0.00000001)
	{
		curValue = lower+(upper-lower)/2;
		if(curValue*curValue < num)
			lower = curValue;
		else
			upper = curValue;
	}
	return curValue;
}

int main()
{
	double x;
	std::cin >> x;
	std::cout << x << "的平方根是 " << rootbinarysearch(x);
	return 0;
}           

複制

遞歸求解：

/**
 * @description: 求根号n，遞歸法
 * @author: michael ming
 * @date: 2019/4/15 23:05
 * @modified by: 
 */
#include <iostream>
double rootbinarysearch_R(double num, double upper, double lower)
{
    if(num == 1)
        return 1;
    if(lower > upper)
        std::swap(lower,upper);
    double curValue = lower+(upper-lower)/2;
    if(upper-lower < 0.00000001)
        return curValue;
    if(curValue*curValue < num)
        return rootbinarysearch_R(num,curValue,upper);
    else
        return rootbinarysearch_R(num,lower,curValue);
}

int main()
{
    double x;
    std::cin >> x;
    std::cout << x << "的平方根是 " << rootbinarysearch_R(x,x,1);
    return 0;
}           

複制