# 0069. Sqrt(solutions/x)

https://leetcode.com/problems/sqrtx

## Description

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.

\*\*Note:\*\*You are not allowed to use any built-in exponent function or operator, such as `pow(x, 0.5)` or `x ** 0.5`.

**Example 1:**

```
**Input:** x = 4
**Output:** 2
```

**Example 2:**

```
**Input:** x = 8
**Output:** 2
**Explanation:** The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
```

**Constraints:**

* `0 <= x <= 231 - 1`

## ac

```java
class Solution {
    public int mySqrt(int x) {
        // edge case
        if (x < 0) throw new IllegalArgumentException("must greater than 0");
        if (x == 0) return 0;

        // binary search
        int l = 0, r = x;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (mid == x / mid) return mid;
            if (mid < x / mid) {
                l = mid;
            } else {
                r = mid;
            }
        }

        // final check
        return r == x / r ? r : l;
    }
}
```
