**source:**https://leetcode.com/problems/sqrtx/**C/C++**

**Solution to LeetCode**problem

**69**.

**Sqrt(x)**.

## Problem

Given a non-negative integer `x`

, return *the square root of x rounded down to the nearest integer*. The returned integer should be

**non-negative**as well.

You must not use any built-in exponent function or operator.

- For example, do not use
`pow(x, 0.5)`

in c++ or`x ** 0.5`

in python.

## Examples

**Example 1:**

Input:x = 4

Output:2

Explanation:The square root of 4 is 2, so we return 2.

**Example 2:**

Input:x = 8

Output:2

Explanation:The square root of 8 is 2.82842…, and since we round it down to the nearest integer, 2 is returned.

## Constraints

`0 <= x <= 2`

^{31}- 1

## Solution

This can be solved with **Binary Search** where the `mid`

value is the candidate `sqrt`

.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
int mySqrt(int x) {
int l=0;
int r=x;
int res = 0;
while (l<=r) {
long int m = (l+r) / 2;
if ((m*m) == x)
return m;
else if ((m*m) > x)
r = m - 1;
else {
l = m + 1;
res = m;
}
}
return res;
}
};