Sqrt(x)

easy binary search math

Problem

Given a non-negative integer x, compute and return the square root of x. Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

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;
}

Explanation

We want the biggest whole number whose square does not go past x. Instead of testing 0, 1, 2, ... one at a time, we use binary search to zero in on the answer much faster.

The candidate answer lives somewhere in [0, x]. We keep a window [lo, hi] and look at the middle mid. If mid * mid <= x, then mid is a valid answer so far, so we remember it in ans and search the right half for something even bigger. Otherwise mid is too large and we search the left half.

This works because the squares only grow as the number grows, so once a value is too big, everything to its right is too big as well. That lets us throw away half the range each step.

Example: x = 24. The range starts at [0, 24]. mid = 12 gives 144 > 24, too big, so go left. Eventually mid = 4 gives 16 <= 24 (record 4 and go right), while 5 gives 25 > 24. The largest that fits is 4, which is the answer.

Because we halve the search range each time, this finishes in about log x steps instead of x.

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