IMO, if we change the feasible function to i^2 <=n, the code gets simpler as follow:

if (n == 0) return 0;
int left = 1;
int right = n;
int res = -1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(mid <= n / mid) {
res = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return res;

function squareRoot(n) {
if(n===0) return 0
let left = 1
let right = n
let first = 0
while(left<=right){
let mid = Math.floor((left+right)/2)
if(mid**2===n){
return mid
}else if(mid**2<n){
first = mid
left = mid + 1
}else{
right = mid - 1
}
}
return first
}

This is similar to my Java code as well, I’m wondering about flaws here or if this is less efficient than the solution?

public static int squareRoot(int n) {
int left = 0, sqRoot = n, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
int exp = mid * mid;
if (exp == n) return mid;
else if (exp < n) {
sqRoot = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return sqRoot;
}

I think it makes more sense mapping (mid*mid) <= n as “true” and finding the righmost “true” in the boolean mapping rather than what the explanation is saying

I recognize the overall goal here is to teach pattern recognition to quickly solve an algorithm, as in this case, recognizing that you can solve it by recycling the binary search solution. However, I wanted to point out you can optimize this solution by recognizing that for n >= 4, the square root will be less than half of n. In this case, we can add an extra check for when n = 1, and allow the logic of the while loop to correctly identify the square root of n = 2 and n = 3 rounds down to 1 when setting right to 1.

Spoiler Solution

function squareRoot(n) {
if (n === 0 || n === 1) return n;
let left = 1;
let right = Math.floor(n / 2);
let res = -1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (mid**2 === n) {
return mid;
} else if (mid**2 > n) {
res = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return res - 1;
}

public static int squareRoot(int n) {
int l = 1, r = n;
while (l <= r) {
int mid = l + (r - l) / 2;
if (mid == n / mid) return mid;
else if ( mid > n / mid) r = mid - 1;
else l = mid + 1;
}
return r;
}

public static int squareRoot(int n) {
int left = 0, right = n, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid * mid == n) {
return mid;
} else if (mid * mid > n) {
right = mid - 1;
} else {
ans = mid;
left = mid + 1;
}
}
return ans;
}