# 69 Sqrt(x)

Implement`int sqrt(int x)`.

Compute and return the square root of x.

**The Idea:** The naive solution would be to return the first index in the for loop through x where $$i*i=x$$, since $$\sqrt{x} = i*i$$. With binary search, the idea is the same except that we begin our search within the bounds of `[0, x]`, and eliminate the left or right half depending on whether the algorithm overestimated or underestimated the solution.

Below, when `pow < x`, we know this resulted in a underestimation so the next iteration will extend `[mid+1, high]`.

**Complexity:** O(log(x)) time and O(log(x)) space

```cpp
int mySqrt(int x)
{
    if (x == 0 || x == 1) return x;

    long long start = 1, end = x, mid, pow, ans;
    while (start <= end)
    {
        mid = (start + end) / 2;
        pow = mid*mid;

        if (pow == x) return mid;
        else if (pow < x) {
            start = mid + 1;
            ans = mid;
        }
        else end = mid - 1;

    }
    return ans;
}

int main()
{
    cout << mySqrt(2) << endl;
    cout << mySqrt(1) << endl;
    cout << mySqrt(2147483647) << endl;
}
```

**Recursive Python Solution**

```python
import math


class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """

        def b_search(left, right):
            mid = int(left + (right - left) / 2)
            cur = math.pow(mid, 2)
            over = math.pow(mid + 1, 2) # when this over estimates but cur does not, then we found our solution
            if cur <= x < over:
                return int(mid)
            elif math.pow(mid, 2) > x:  # over estimation
                return b_search(left, mid - 1)
            else:
                return b_search(mid + 1, right)  # under estimation

        return b_search(0, x)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/69-sqrtx.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.