有趣的算法问题11——X的平方根（二分查找法）_随机算法求平方根

有趣的算法问题11——X的平方根（二分查找法）

这个可能是我写的最气的博客，没有之一了，为什么气，大家往下面看就知道了……
所有的算法均用C++编写
所有的题目均来自计蒜客
说的是二分法，结果也不一定就是用了二分法……

题目

设计函数int sqrt(int x)，计算 x 的平方根。

输入格式

输入一个 整数 x，输出它的平方根。直到碰到文件结束符（EOF）为止。
//在windows平台EOF为ctrl+Z ,C用这个while(scanf("%d",&num)!=EOF){}，C++用 while(cin>>num){} 就可以了。num是你要输入的数

输出格式

对于每组输入，输出一行一个整数，表示输入整数的平方根。

形如：
样例输入
1
2
3
4
5
6
7
8
9

样例输出
1
1
1
2
2
2
2
2
3

刨坑点

1.啥是二分查找？
二分查找就是我们当年在学数据结构的时候查找里的二分查找，有个low,up,mid，up从最后一个开始，low从第一个开始，mid=(low+up)/2; 每次看你的mid中的数是不是你要的那个数，如果不是就看看数是大了，还是小了，如果mid小了就把low的边际换成大的，low=mid+1; 或者 low=mid; 都是可以的，如果mid大了就把up的边际换成小的， up=mid-1; 或者 up=mid; 都行，前提是在low<=up 的情况下。直到最后你的下标越界或者找到了。

2.还有这道题是求平方我们可以做的灵活一点不必要这个用传统的二分，可以这个设置条件 if(i*i<=x&&(i+1)*(i+1)>x) //x是我们要求平方根的数，i是平方根
满足这个条件是为平方根复合2^2<6<3^2，那么6的平方根就为2

槽点

这道题不要以为简单我们认真看一下它的时间复杂度和空间复杂度还有通过率

主要是时间复杂度，真的让你好气喔~！
我写了n个代码它每次都说我是超时了，或者段错误//段错误有错误的赋值，访问错误内存等等
我真的…

吓得我马上去百度了一下，我发现大家跟我编的差不多好吗，这些不都是不能通过编译吗……超时啊!大哥,你们还堂而皇之的把代码po出来。
这样你去计蒜客的编译器下面走一圈根本通不过好吗……这样很尴尬好吗……
还有想知道我最后是怎么解决的吗？我真的好想一巴掌拍下去，肯定能拍死一只苍蝇[那个表情包]……

就是我用了cmath包里的sqrt(int)函数然后强转成int输入，是不是很尴尬，我真的给自己加了那么多freestyle……但是编译器都不认……

代码

1.这个代码用了1110ms，它的亮点就在if(i*i<x+1&&(i+1)*(i+1)>x)

#include <iostream>
using namespace std;
int sqrt(int x);
int main(){
    int num;
    int i=0;
    int j=0;
    int array[20];
    while(scanf("%d",&num)!=EOF){
        array[i]=sqrt(num);
        i++;
    }
    for(;j<i;j++){
        cout<<array[j]<<endl;
    }
    return 0;
}
int sqrt(int x){
    int i=1;
    for(;i<x/2;i++){
        if(i*i<x+1&&(i+1)*(i+1)>x){
            break;
        }   
    }
    return i;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2.这段代码的亮点就在于我用的时二分法写的，但是我还是超时了，这道题用二分法必超时，因为我写了很多种二分法，这是我写的最简洁的了2000ms……

#include <iostream>
using namespace std;
int sqrt(int x);
int main(){
    int num;
    int i=0;
    int j=0;
    int array[20];
    while(scanf("%d",&num)!=EOF){
        array[i]=sqrt(num);
        i++;
    }
    for(;j<i;j++){
        cout<<array[j]<<endl;
    }
    return 0;
}
int sqrt(int x){
    int low=1;
    int up=x;
    int mid;
    while(low<=up){
        mid=(low+up)/2;
        if(mid*mid<=x&&(mid+1)*(mid+1)>x){
            break;
        }
        else if(mid*mid>x){
            up=mid;
        }
        else{
            low=mid;
        }
    }

        return mid;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

3.这段代码没有亮点，就是我超时了，我把以前能节约时间而我没有节约时间的部分都改成节约时间的了

#include <iostream>
using namespace std;
int sqrt(int x);
int main(){
    int num;
    while(scanf("%d",&num)!=EOF){
        cout<<sqrt(num)<<endl;
    }
    return 0;
}
int sqrt(int x){
    int i=1;
    for(;i<=x/2;i++){
        if(i*i<=x&&(i+1)*(i+1)>x){
            break;
        }
    }
        return i;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4.这段代码是运行通过的，用cmath包里的sqrt(int)函数，但是这是不是根题矛盾了，题不是说自己写一个sqrt(int)函数吗？我真没的好无语

#include <iostream>
#include <cmath>
using namespace std;
int main(){
    int num;
    while(cin>>num){
        cout<<(int)sqrt(num)<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

测试

测试成功！~