current position:Home>69. Sqrt (x) (c + + problem solving version with vs runnable source program)

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

2022-01-27 04:37:35 Bufan

69. Sqrt(x)(C++ The problem solving version contains VS Can run the source program )

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

copyright notice
author[Bufan],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201270437295876.html