1. Answer key

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;
}