# 69. Sqrt(x)

🟩 Easy

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.

## 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`

## Hint-1

> Try exploring all integers. (Credits: @annujoshi)

## Hint-2

> Use the sorted property of integers to reduced the search space. (Credits: @annujoshi)

## Solution

My Solution

```go
func mySqrt(x int) int {

    mid, left, right := 0, 0, x+1    
    for left < right {
        mid = left + (right-left)/2
        if mid * mid > x {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left - 1
}
```

Optimal Solution (Binary Search)

```go
func mySqrt(x int) int {
    if x < 2 {
        return x
    }
    
    left, right := 1, x/2
    
    for left <= right {
        mid := left + (right-left)/2
        square := mid * mid
        
        switch {
        case square == x:
            return mid
        case square < x:
            left = mid + 1
        default:
            right = mid - 1
        }
    }
    
    return right
}
```

### Approach

This solution uses binary search to efficiently find the square root:

1. Initial Range:
   * For x ≥ 2, square root is in range \[1, x/2]
   * For x < 2, return x directly
   * Using x/2 as upper bound since √x ≤ x/2 for x ≥ 4
2. Binary Search Implementation:
   * Calculate mid point and its square
   * If square equals x, found exact square root
   * If square less than x, search right half
   * If square greater than x, search left half
3. Key Insights:
   * Integer overflow avoided using (right-left)/2
   * Result is floor of actual square root
   * Right pointer ends at floor value

### Complexity Analysis

#### Time Complexity: O(log n)

* Binary search over range \[1, x/2]
* Search space halved in each iteration
* Takes log₂(x) steps to converge

#### Space Complexity: O(1)

* Only uses constant extra space:
  * Three integers (left, right, mid)
  * One temporary for square calculation

### Why it works

* Binary Search Properties:
  * Search space is sorted (1 to x/2)
  * Can compare mid² with target
  * Always converges to floor value
* Handling Edge Cases:
  * x < 2 handled separately
  * Overflow prevented in mid calculation
  * Right pointer gives floor value when no exact square
* Correctness:
  * If exact square root exists, found directly
  * If not, right pointer gives floor value
  * All values in \[1, x/2] considered

![result](https://600345290-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FrSK2xH3txU3tYyDsT8mQ%2Fuploads%2Fgit-blob-5ddfd052552702fd1c989dcfceda2f9324e1f8a8%2F69.png?alt=media)

Leetcode: [link](https://leetcode.com/problems/sqrtx/description/)