> For the complete documentation index, see [llms.txt](https://ugopireddy.gitbook.io/leet-code-solutions/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ugopireddy.gitbook.io/leet-code-solutions/solutions_51_-_100/69_sqrtx__medium.md).

# 69 Sqrt(x) – Medium

### Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

### Thoughts:

The most straight forward way it so iterate over all possible numbers, namely 1 to x/2+1.

But we could find it faster by using binary search. improving running time from O(x) to O(logx).

Plus, the condition to determine result is also critical, because we cannot say m\*m == x is the checking condition.

### Solutions:

```java
public class Solution {
    public int mySqrt(int x) {
        int left = 1, right = x/2;
        while ( left <= right) {
            int mid = (left + right) /2;
            if (mid > x /mid) {
                right = mid - 1;
                continue;
            }
            if ((mid+1) <= x/(mid+1)) {
                left = mid + 1;
                continue;
            }
            return mid;
        }
        return x;
    }
}
```