How do you solve Sqrt(x)?

Use a binary search with pointers left = 0 and right = x. Calculate mid = (left + right) // 2 and mid^2. If mid^2 equals x, return mid immediately. If mid^2 < x, move left to mid + 1 to search higher values. Otherwise, move right to mid - 1 to search lower values. When the loop ends, right points to the floor of the square root.

Sqrt(x)

Q: What is the time complexity of Sqrt(x)?

O(log x). Each iteration halves the search space between left and right, leading to logarithmic time relative to x.

Q: What pattern does Sqrt(x) use?

The Pattern: Modified Binary Search (Search for Integer Square Root) The Heuristic: When searching for an integer value satisfying a monotonic condition (like mid*mid <= x), use binary search to narrow the range by comparing mid^2 to x, adjusting boundaries accordingly until convergence.

Easy Modified Binary Search

Problem

Given a non-negative integer x, return the integer part of the square root of x (i.e., floor of the square root).

0 ≤ x ≤ 2³¹ - 1

Example

Input: x = 8

Output: 2

The exact square root of 8 is approximately 2.8284. The algorithm uses a binary search between 0 and 8 to find the integer part. It checks midpoints and their squares, narrowing the search space. When the search completes, it returns 2, the floor of the square root.

Approach

Straightforward Solution

A naive approach would be to iterate from 0 up to x, checking each number's square until exceeding x. This is O(x) time, which is inefficient for large x.

Core Observation

The square root of a number x lies between 0 and x (inclusive). The function f(mid) = mid * mid is monotonic increasing for mid >= 0, allowing binary search to efficiently find the integer square root.

Path to Optimal

Recognizing the monotonic nature of mid^2 allows the use of binary search. By repeatedly halving the search space and comparing mid^2 to x, the algorithm quickly converges to the integer square root in O(log x) time.

Optimal Approach

Preview

Use a binary search with pointers left = 0 and right = x. Calculate mid = (left + right) // 2 and mid^2…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log x)

Each iteration halves the search space between left and right, leading to logarithmic time relative to x.

Space

O(1)

Only a fixed number of variables (left, right, mid, sq) are used, requiring constant auxiliary space.

Pattern Spotlight

Modified Binary Search (Search for Integer Square Root)

When searching for an integer value satisfying a monotonic condition (like mid*mid <= x), use binary search to narrow the range by comparing mid^2 to x, adjusting boundaries accordingly until convergence.

Solution

Python

1class Solution:
  def mySqrt(self, x: int) -> int:
      
      left, right = 0, x
5
      while left <= right:
          
          mid = (left + right) // 2
          sq = mid * mid
10
          if sq == x:
              return mid
          elif sq < x:
              left = mid + 1
          else:
              right = mid - 1
17
      return right

Step-by-Step Solution

Initialize Binary Search Boundaries

4	`left, right = 0, x`

Objective

To set the initial search range for the integer square root between 0 and x.

Key Insight

The square root of x cannot be greater than x itself, so initializing left to 0 and right to x covers the entire possible range. This sets the stage for a binary search that will efficiently narrow down the correct integer root.

Interview Quick-Check

Core Logic

Setting left = 0 and right = x ensures the search space includes all possible integer square roots.

Perform Binary Search to Narrow Down Integer Square Root

To iteratively adjust the search boundaries based on the square of the midpoint until the integer square root is found.

Return the Floor of the Square Root After Search Completion

To return the greatest integer whose square is less than or equal to x after the binary search loop ends.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 11 Critical

if sq == x:

Check whether mid squared equals x.

If mid squared equals x, an exact integer square root has been found and the search can terminate immediately.

Line 18 Critical

return right

Return right as the integer square root of x.

When the loop terminates, right points to the greatest integer whose square does not exceed x, which by definition is the floor of the square root.

Full line-by-line criticality + rationale for all 11 lines available on Pro.

Test Your Understanding

Why does the algorithm return 'right' after the binary search loop instead of 'left'?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Sqrt(x) from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Sqrt(x) drill

or drill a free problem

1	`class Solution:`
2	`def mySqrt(self, x: int) -> int:`
3
4	`left, right = 0, x`
5
6	`while left <= right:`
7
8	`mid = (left + right) // 2`
9	`sq = mid * mid`
10
11	`if sq == x:`
12	`return mid`
13	`elif sq < x:`
14	`left = mid + 1`
15	`else:`
16	`right = mid - 1`
17
18	`return right`