---
tags: data_structure_python
---

# Sqrt(x) <img src="https://img.shields.io/badge/-easy-brightgreen">

Implement ```int sqrt(int x)```.

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

<ins>**Example 1:**</ins>

>Input: 4
>Output: 2

<ins>**Example 2:**</ins>

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

# Solution

class Solution:
    def mySqrt(self, x: int) -> int:
        l = 0
        r = x
        
        while l <= r:
            
            mid = l + (r - l)//2
        
            if x == mid * mid:
                return mid
            elif x > mid * mid:
                l = mid + 1
                ans = mid
            else:
                r = mid - 1
               
        return ans