Integer Square Root

easy binary search math

Problem

Given a non-negative integer x, return the integer part of its square root — the largest integer r with r·r ≤ x. You may not use any built-in sqrt.

Inputx = 24

Output4

Binary search r in [0, x]. The largest r with r·r ≤ x is the answer.

def my_sqrt(x):
    lo, hi, ans = 0, x, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

function mySqrt(x) {
  let lo = 0, hi = x, ans = 0;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (mid * mid <= x) { ans = mid; lo = mid + 1; }
    else hi = mid - 1;
  }
  return ans;
}

class Solution {
    public int mySqrt(int x) {
        long lo = 0, hi = x, ans = 0;
        while (lo <= hi) {
            long mid = (lo + hi) >>> 1;
            if (mid * mid <= x) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        return (int) ans;
    }
}

int mySqrt(int x) {
    long lo = 0, hi = x, ans = 0;
    while (lo <= hi) {
        long mid = (lo + hi) / 2;
        if (mid * mid <= x) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    return (int) ans;
}

Time: O(log x) Space: O(1)