> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/binary-search/69-sqrtx.md).

# 69 Sqrt(x)

## 69. [Sqrt(x)](https://leetcode.com/problems/sqrtx/description/)

## 1. Question

Implement`int sqrt(int x)`.

Compute and return the square root ofx.

**x** is guaranteed to be a non-negative integer.

**Example 1:**

```
Input: 4

Output:2
```

**Example 2:**

```
Input: 8

Output: 2

Explanation:
The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will betruncated.
```

## 2. Implementation

**(1) Binary Search**

思路：由于这题要求结果是整数，这就相当于找一个整数num <= sqrt(x), 是找右边界， 可以直接套用二分法的找右边界的模板

```java
class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        int start = 1, end = x, mid = 0;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;

            if (mid > x / mid) {
                end = mid - 1;
            }
            else {
                start = mid;
            }
        }

        if (end <= x / end) {
            return end;
        }
        else {
            return start;
        }
    }
}
```

## 3. Time & Space Complexity

**Binary Search:** 时间复杂度O(logx), 空间复杂度O(1)