# 69. Sqrt (x) (c + + problem solving version with vs runnable source program)

2022-01-27 04:37:35 Bufan

## 1.1 violence

• Direct traversal , Note that the value of the stored square is long long.
• Method 2 is also traversal , However, the search space has been reduced a lot , So the speed is also very fast .

## 1.2 Dichotomy search

• For a nonnegative number n, Its square root will not be greater than （n/2+1）;
• stay [0, n/2+1] Within this range, binary search can be carried out , Find out n The square root of .

# 2. Power button C++ Source code

## 2.1 violence

``````class Solution {

public:
int mySqrt(int x) {

for (long long int i = 0; i <= x; i++) {

long long int s = i * i;
if (s == x)return i;
else if (s > x)return i - 1;
}
return 0;
}
};
``````

## 2.2 Dichotomy

``````class Solution {

public:
int mySqrt(int x) {

long long int left = 0;
long long int right = x / 2 + 1;
long long int mid = 0;
long long int mul = 0;
while (left < right) {

mid = (left + right) / 2;
mul = mid * mid;
if (mul < x)left = mid + 1;
else if (mul > x)right = mid - 1;
else return mid;
}
return left * left <= x ? left : left - 1;
}
};
``````

# 3.VS Can run the source program

``````#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<algorithm>
#include<math.h>
#pragma warning(disable:4996)
using namespace std;

class Solution {

public:
int mySqrt(int x) {

// Traverse （ violence ） use long long
/*for (long long int i = 0; i <= x; i++) { long long int s = i * i; if (s == x)return i; else if (s > x)return i - 1; } return 0;*/

// Two points search
long long int left = 0;
long long int right = x / 2 + 1;
long long int mid = 0;
long long int mul = 0;
while (left < right) {

mid = (left + right) / 2;
mul = mid * mid;
if (mul < x)left = mid + 1;
else if (mul > x)right = mid - 1;
else return mid;
}
return left * left <= x ? left : left - 1;
}
};
int main()
{

printf(" Enter a non negative integer ：");
int x;
scanf("%d", &x);
Solution test;
int ans = test.mySqrt(x);
printf(" Its arithmetic square root （ Integral part ） by ：%d", ans);

printf("\n");
system("pause");
return 0;
}
``````