int sqrt(int x) {
if (x == 0)
return x;
int left = 1, right = x;
while (true) {
int mid = (left + right) / 2;
if (mid > x / mid)
right = mid - 1;
else if (mid + 1 > x / (mid + 1)) //mid < x / mid
return mid;
else
left = mid + 1;
}
}

BY Best Interview Question ON 26 Jan 2020