本文共 1442 字，大约阅读时间需要 4 分钟。

二分查找：

1. 数据需要是顺序表（数组）
2. 数据必须有序
3. 可以一次排序，多次查找；如果数据频繁插入，删除操作，就必须保证每次操作后有序，或者查找前继续排序，这样成本高，二分查找不合适
4. 数据太小，不用二分查找，直接遍历
5. 数据太大，也不用，因为数组需要连续的内存，存储数据比较吃力
6. 复杂度 lg₂n

题目： 求一个数的平方根

• 例如：二分法求根号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
   
    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 
   
    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;}
   

转载地址：https://michael.blog.csdn.net/article/details/89320746 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！