#include <iostream>
using namespace std;

int mySqrt(int x) {
	if(x <= 1){
		return x;
	}
	int low = 0, high = x / 2;
	//long to prevent overflow
	long long mid;
	while(low <= high){
		mid = (low + high) / 2;
		//needs to be long to prevent overflow
		long long t = mid * mid;
		//second part is to return floor if x is not perfect square
		if( t == x || ((t < x) && ((mid + 1) * (mid + 1) > x))){
			break;
		} else if(x < t){
			high = mid - 1;
		}else{
			low = mid + 1;
		}
	}
	return mid;
}

int main() {
	cout << mySqrt(16) << endl;
	cout << mySqrt(27) << endl;
	return 0;
}