DSA sheet · Binary Search · Classic binary search pattern

Sqrt(x)

Second question of the classic pattern (LeetCode 69). Find the square root of x, rounded down, without using any built-in square root or power function. There is no array here. The teacher draws the numbers 1, 2, 3, … on a number line and notices that this line is already sorted, so we can binary search over numbers instead of indexes.

Along the way she explains four ideas that come back again and again: (1) how to pick a tighter search range (up to x/2, and why not x/3), (2) base cases, (3) why mid is written as left + (right - left) / 2, derived on the number line, and (4) overflow when squaring big numbers in Java, which she hits live in the video and fixes.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: try 1, 2, 3, … one by one
• Part B · Binary search on the number line
• Part C · Revision page

Part 0 · Before starting

Square, square root, rounded down

• The square of m is m × m. e.g. 3² = 9.
• The square root of x is the number r with r × r = x. e.g. √9 = 3. For most x it isn't a whole number: √8 ≈ 2.83.
• Rounded down (floor) means "drop the decimal part": 2.83 → 2. In other words, we want the biggest whole number m with m × m ≤ x.

Why binary search works here

Binary search needs a sorted order or a yes/no question that flips only once. Ask "is m × m ≤ x?" for m = 1, 2, 3, …:

Squares grow as m grows, so the answers are yes yes … yes no no …. It flips only once (it's monotonic). So at any mid, comparing mid² with x tells us which side to keep.

low/high and the mid formula

left and right mark the ends of the range of numbers we're still considering. mid is the number halfway between them. We compute it as mid = left + (right - left) // 2. The teacher derives why in Part B, step 4. In short: in Java/C++, left + right can go past the int limit 2³¹ − 1 and become negative (overflow). Python ints never overflow, so in Python it's only a good habit.

Part A · Brute force: try 1, 2, 3, … one by one

LeetCode 69

1The question in simple words

You get a non-negative integer x (0 or more). Return the square root of x rounded down to a whole number. The answer is non-negative too. You may not use built-ins like math.sqrt, x ** 0.5 or pow.

• x = 4 → 2 (exact)
• x = 8 → √8 ≈ 2.83 → 2
• x = 25 → 5

2What the constraints tell us

• 0 ≤ x ≤ 2³¹ − 1. Two things follow.
• x can be 0 (and 1) → we'll need base cases.
• x can be the maximum int (2³¹ − 1 = 2,147,483,647). In Java/C++, adding even 1 to that turns it negative. So anything that adds or multiplies near this size must use a bigger type (long). The teacher stresses: whenever you add to or multiply values near the int max, prefer long. In Python this doesn't apply, because ints grow as needed.

3Intuition

The answer is the last m whose square is still ≤ x. So start at 1 and keep going up while the square is still ≤ x. The teacher mentions that this problem can be solved without binary search, and that the point of the video is to learn to think of binary search in such cases.

4Building the logic

• Keep a counter m = 1. While (m + 1)² ≤ x, move m up by one.
• When the next square would be too big, m is the answer.
• x = 0 is special: the answer is 0, not 1.

5Approach steps

1. If x < 2, return x.
2. m = 1. While (m + 1) × (m + 1) ≤ x: m += 1.
3. Return m.

6Code (Python)

class SolutionBrute:
    def mySqrt(self, x):
        if x < 2:
            return x                    # sqrt(0) = 0, sqrt(1) = 1
        m = 1
        while (m + 1) * (m + 1) <= x:   # next number still fits
            m += 1
        return m

7Code line by line

8Dry run

x = 8: m = 1 → is 2² = 4 ≤ 8? yes → m = 2 → is 3² = 9 ≤ 8? no → return 2 ✓.

9Complexity & remember

• Time O(√x): the loop runs about √x times. For x = 2³¹ − 1 that's about 46,000 steps, which passes, but it's not the binary search way.
• Space O(1).

Part B · Binary search on the number line

1The question

Same question. Find the biggest m with m × m ≤ x, in O(log x) steps.

2What the constraints tell us

Same as Part A. Here they matter even more. right can be up to about 2³⁰, so in Java/C++ both left + right and mid * mid can overflow an int. In Python neither can.

3Intuition: the number line is a sorted array

Draw the numbers 1 2 3 4 5 6 7 8 on a line. For x = 8, can 7 be the square root? No, 7² = 49. Can 6? No. 5? No. The answer sits somewhere around 2 or 3. For x = 25, the line goes up to 25, and 10 or 14 are obviously too big. The answer, 5, is far to the left. For x = 4, the answer is 2.

These numbers are in sorted order, just like a sorted array. So instead of walking them one by one, jump to the middle number, square it, and compare with x. Too small → go right. Too big → go left.

4Building the conditions from examples

Idea 1: the right end can be x/2, not x

In all those examples the square root was well to the left of x. The teacher's claim: the square root is always ≤ x/2, so we can start right at x // 2 instead of x. That's one fewer halving, and it keeps the numbers smaller.

Idea 2: base cases for 0 and 1

If x is 0, the root is 0. If x is 1, the root is 1. So when x < 2, return x itself.

Idea 3: why mid = left + (right - left) / 2 (her number-line derivation)

Earlier (in Binary Search Basics) we used (left + right) / 2, because the values were small. Here right can be close to 2³¹ − 1, the biggest int in Java. Adding left to it can push past the maximum and give a negative number. So we need a formula that gives the same middle without adding two big numbers.

Her derivation: put left at 3 and right at 8 on the line.

  1   2   3   4   5   6   7   8
          L           m       R
          |<-- (R - L) = 5 -->|
          |<- 5/2 ->|

• Usual way: (3 + 8) / 2 = 11 / 2 = 5.5 → 5.
• Other way: the middle is surely to the right of L. Start at L, then walk half the distance from L to R. The distance is R − L = 5. Half of it is 2.5. So mid = L + (R − L) / 2 = 3 + 2.5 = 5.5 → 5. Same answer ✓.

R - L is never bigger than R, so this never creates a number bigger than the inputs. That's why we use it whenever x is so big that one more addition could make it negative.

Idea 4: compare mid² with x (three cases)

Let square = mid * mid. The target we compare with is x.

• square == x → mid is the exact square root → return mid.
• square < x → mid is too small; we need a bigger number to square → left = mid + 1.
• square > x → mid is too big; we need a smaller number → right = mid - 1.

While explaining, she says "square less than mid" once; she means "square less than x". The code compares with x.

Idea 5: loop while left <= right, then return right

If x isn't a perfect square (like 8), the equal case never happens. left keeps moving right and right keeps moving left, until they cross. Then the loop stops. Which one is the answer?

• When they cross, left is ahead and right is behind (right = left − 1).
• The true root lies between them: for 8, it's 2.83, between right = 2 and left = 3.
• The question wants it rounded down, which is the smaller one → return right.

Idea 6: overflow in mid × mid (the bug she hits live)

In Java she first stored mid * mid into a long variable, but still got a wrong answer on a big test. The reason: mid was an int, so int × int is computed as an int first. It overflows before being stored in the long. Saving it into a long afterwards is too late.

Her fix: make mid a long (and so left and right too, since they get assigned from mid), and cast back to int when returning. She also had a small typo along the way: she forgot to write mid in the return cast, got a compile error, and fixed it.

5Approach steps

1. If x < 2 → return x.
2. left = 1, right = x // 2.
3. While left <= right: mid = left + (right - left) // 2, square = mid * mid.
4. square == x → return mid. square < x → left = mid + 1. Else → right = mid - 1.
5. After the loop → return right (the rounded-down root).

6Code (Python)

class Solution:
    def mySqrt(self, x):
        if x < 2:
            return x                     # 0 -> 0, 1 -> 1
        left, right = 1, x // 2          # the root is never above x/2
        while left <= right:
            mid = left + (right - left) // 2
            square = mid * mid           # Python ints don't overflow
            if square == x:
                return mid               # perfect square
            elif square < x:
                left = mid + 1           # need a bigger number
            else:
                right = mid - 1          # need a smaller number
        return right                     # crossed: right = floor(sqrt(x))

7Code line by line

8Dry run

Her example: x = 8

A perfect square: x = 16

The biggest input: x = 2,147,483,647

right starts at 1,073,741,823. About 30 halvings later, the loop ends with right = 46340 (46340² = 2,147,395,600 ≤ x, while 46341² = 2,147,488,281 > x). In Java, 46341² is bigger than the int max, which is exactly where the int × int overflow bites.

9Complexity & remember

• Time O(log x): the range 1 … x/2 halves every step. x can be up to 2³¹, so that's at most about 31 steps.
• Space O(1).

Part C · Revision page

s = Solution()
for x in [0, 1, 4, 6, 8, 16, 25, 2147483647]:
    print(x, s.mySqrt(x), SolutionBrute().mySqrt(x))
# 0 0 0 / 1 1 1 / 4 2 2 / 6 2 2 / 8 2 2 / 16 4 4 / 25 5 5 / 2147483647 46340 46340

Based on this video: Sqrt(x) | Classic Binary Search pattern