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

# Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

## Example

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

## Solution

binary search start + 1 < end is a template method, in the end, the start ajacent with end, so if end <= x return end or return start.

why check end <=x first becasue the end it's closing the x after do end \* end so that 's the best solution.

```
class Solution:
    """
    @param x: An integer
    @return: The sqrt of x
    """
    def sqrt(self, x):
        if x <= 0:
            return 0
        start, end = 1, x

        while start + 1 < end:
            mid = (start + end) / 2
            if mid *  mid <= x:
                start = mid
            else:
                end = mid

        return start
```