---

Intuition

To find the square root of a number x, we need the largest integer n such that (n^2 \leq x). Since the square root is monotonic (i.e., increasing as x increases), binary search is a natural choice to efficiently find the answer without testing every possible value from 0 to x.

---

Approach

1. Binary Search Setup:

   • Initialize left to 0 and right to x. The answer will lie between these two values.

   • Use a variable result to store the current best approximation of the square root.

2. Binary Search Execution:

   • Calculate the mid-point mid as ((\text{left} + \text{right}) // 2).

   • If ( \text{mid}^2 > x ), the square root must be smaller, so adjust the right boundary to mid - 1.

   • If ( \text{mid}^2 < x ), the square root must be larger, so adjust the left boundary to mid + 1 and update result to mid (current best approximation).

   • If ( \text{mid}^2 == x ), return mid directly as it’s an exact match.

3. Return Approximation:

   • After the loop, return the result, which will contain the largest integer (n) such that (n^2 \leq x).

---

Complexity

• Time complexity:
  $$O(\log x)$$
  The binary search reduces the search space by half at each iteration, resulting in a logarithmic time complexity.

• Space complexity:
  $$O(1)$$
  The solution uses a constant amount of extra space, regardless of the size of x.

---

Code

class Solution(object):
    def mySqrt(self, x):
        left, right = 0, x
        result = 0
        while left <= right:
            mid = (left + right) // 2

            if mid**2 > x:  
                right = mid - 1

            elif mid**2 < x:         
                left = mid + 1
                result = mid
            else:
                return mid

        return result

---

Example Test Cases

1. Input: x = 4
   Output: 2
   Explanation: The square root of 4 is exactly 2.

2. Input: x = 8
   Output: 2
   Explanation: The square root of 8 is approximately 2.83, and the largest integer less than or equal to 2.83 is 2.

3. Input: x = 0
   Output: 0
   Explanation: The square root of 0 is 0.

4. Input: x = 1
   Output: 1
   Explanation: The square root of 1 is exactly 1.

---

Connect with Me

If you found this solution helpful, feel free to connect with me on LinkedIn! Let’s grow and share knowledge together. 😊

---