1
lo
Compute the integer square root of x — the floor of √x — without a built-in sqrt. Because mid·mid increases monotonically, you can binary search the answer in [0, x] in O(log x).
Given a non-negative integer x, return floor(√x)— the largest integer whose square does not exceed x— without any built-in sqrt or power operator. For example, x = 8 → 2, because 2·2 = 4 ≤ 8 but 3·3 = 9 > 8. And x = 16 → 4 (exact square).
true for every small mid and flips to false once mid grows past √x. That monotone true→false boundary is exactly what binary search finds. Search candidate answers in [0, x], and keep the largest mid whose square still fits.x < 2 (i.e. 0 or 1), floor(√x) = x. Return early so mid = 0 never appears in the overflow-safe division.lo = 1, hi = x, ans = 1. The true answer lies somewhere in this inclusive window.mid = lo + Math.floor((hi - lo) / 2)— the overflow-safe midpoint.mid·mid ≤ x as mid <= x / mid so the product never overflows. If it holds, mid is a valid floor: record ans = mid and search higher with lo = mid + 1. Otherwise mid is too big → hi = mid - 1.ans is the largest mid with mid·mid ≤ x — that is floor(√x).mid * mid ≤ x directly? In fixed-width languages (Java/C++) mid * mid can overflow for large x and silently wrap negative, breaking the comparison. Writing it as mid <= x / mid (or using a 64-bit / BigInt product) keeps every value in range. In JS the number is a 64-bit float, but the idiom is the canonical, language-portable form.Only a few integer variables are needed → O(1)space. Newton's method (r = (r + x / r) / 2 until it stabilises) also runs in roughly O(log x) iterations and O(1) space, but binary search is easier to reason about and to get exactly right.
[1, 8]. lo=1, hi=8, ans=1. Keep the largest mid with mid·mid ≤ 8.1function mySqrt(x: number): number {2 if (x < 2) return x; // 0 -> 0, 1 -> 134▶ let lo = 1;5▶ let hi = x;6▶ let ans = 1;78 while (lo <= hi) {9 const mid = lo + Math.floor((hi - lo) / 2);10 if (mid <= x / mid) { // mid*mid <= x, overflow-safe11 ans = mid; // mid is a valid floor candidate12 lo = mid + 1; // try for something bigger13 } else {14 hi = mid - 1; // mid too big, shrink15 }16 }17 return ans; // largest mid with mid*mid <= x18}
function mySqrt(x: number): number {
if (x < 2) return x; // 0 -> 0, 1 -> 1
let lo = 1;
let hi = x;
let ans = 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (mid <= x / mid) { // mid*mid <= x, overflow-safe
ans = mid; // mid is a valid floor candidate
lo = mid + 1; // try for something bigger
} else {
hi = mid - 1; // mid too big, shrink
}
}
return ans; // largest mid with mid*mid <= x
}x < 2 the floor of the root is x itself. Returning early also guarantees mid ≥ 1 later, so the overflow-safe x / mid never divides by zero.[1, x] for x ≥ 2. ans starts at 1 (always valid since 1·1 = 1 ≤ x) and tracks the best floor found so far.lo <= hi keeps a single-element window in play. mid = lo + Math.floor((hi - lo) / 2) is the overflow-safe midpoint.mid <= x / mid is mid·mid ≤ x written to avoid overflow. When it holds, mid is a feasible floor: save it to ans and push lo right to hunt for something larger.mid·mid > x, every value ≥ mid is also too big, so discard them with hi = mid - 1.lo > hi the window is empty; ans holds the largest mid with mid·mid ≤ x, which is exactly floor(√x).[1, x] halves each iteration. O(1) extra space — only a handful of integer variables.mid <= x / mid not mid * mid <= x?" The product can overflow a 32/64-bit integer for large x; the division keeps operands in range. Alternatively cast to a wider type or use BigInt.r; if r·r !== x, the ceiling is r + 1.r = (r + x / r) / 2 from a guess until it stops decreasing — also O(log x), O(1), but trickier to bound exactly.i from 0 while i·i ≤ x; the last such i is the answer — O(√x).function mySqrt(x: number): number {
if (x < 2) return x; // 0 -> 0, 1 -> 1
let lo = 1;
let hi = x;
let ans = 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (mid <= x / mid) { // mid*mid <= x, overflow-safe
ans = mid; // mid is a valid floor candidate
lo = mid + 1; // try for something bigger
} else {
hi = mid - 1; // mid too big, shrink
}
}
return ans; // largest mid with mid*mid <= x
}[1, x] halves each iteration. O(1) extra space — only a handful of integer variables.Walk i upward while i·i ≤ x; the last such i is the floor of the root.
function mySqrt(x: number): number {
let i = 0;
while (i <= x / Math.max(i, 1) && i * i <= x) i++;
return i - 1 < 0 ? 0 : i - 1;
}√x steps. Binary searching the same range reaches the boundary in O(log x).Iterate r = (r + x / r) / 2 from an over-estimate; it converges quadratically to √x, then floor it.
function mySqrt(x: number): number {
if (x < 2) return x;
let r = x;
while (r > x / r) {
r = Math.floor((r + Math.floor(x / r)) / 2);
}
return r;
}| integer sqrt / floor of a root | binary search the answer in [0, x] |
| monotone "is value feasible?" predicate | binary search on the answer space |
| risk of mid*mid overflow | compare as mid <= x / mid (or BigInt) |
| "largest value satisfying P" | record candidate, then lo = mid + 1 |
function mySqrt(x: number): number {
if (x < 2) return x;
let lo = 1, hi = x, ans = 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (mid <= x / mid) { ans = mid; lo = mid + 1; }
else hi = mid - 1;
}
return ans;
}mid·mid ≤ x is monotone (true for small mid, false past √x), so the boundary can be found by halving the candidate range.x = 8, what does mySqrt return?mid <= x / mid rather than mid * mid <= x?mid·mid ≤ x holds, what does the algorithm do?if (x < 2) return x; included?x = 16, what is returned?