Find Square Root Using Binary Search

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given a non-negative integer x, your task is to find its integer square root. The integer square root of x is the greatest integer r such that r * r ≤ x.

You must solve this problem without using any built-in square root functions. If x is negative, return -1 (square root of negative numbers is not defined in real numbers).

Examples❯

Input (x) Output Description
0 0 Square root of 0 is 0
1 1 Square root of 1 is 1
4 2 Perfect square: 2 * 2 = 4
10 3 3 * 3 = 9, 4 * 4 = 16 > 10. So answer is 3
100 10 Perfect square: 10 * 10 = 100
99 9 9 * 9 = 81, 10 * 10 = 100 > 99. So answer is 9
1000000 1000 Large number, 1000 * 1000 = 1000000
-25 -1 Negative input: square root not defined
-1 Empty input or undefined: treated as invalid

Solution❯

Understanding the Problem

We are given a number x, and we need to compute its integer square root. That means we want the largest integer r such that:

  • r * r ≤ x
  • and (r + 1) * (r + 1) > x

For example, the square root of 10 is approximately 3.16, but since we want only the integer part, we return 3.

This problem becomes interesting when x is very large, because brute force checking every number up to x would be too slow. That’s where binary search helps — it allows us to quickly narrow down our search.

Step-by-Step Solution with Example

Step 1: Identify base cases

First, we handle easy cases directly. If x is 0 or 1, then the square root is just x itself.

Step 2: Initialize binary search range

We set low = 0 and high = x. These define the search range for our answer. We'll repeatedly guess a number mid between low and high.

Step 3: Apply binary search

At each step, we calculate mid = (low + high) / 2, and check mid * mid:

  • If mid * mid == x, then we’ve found the exact square root.
  • If mid * mid < x, it means mid might be the answer, but we try to find a larger one: low = mid + 1.
  • If mid * mid > x, then mid is too large: high = mid - 1.

We keep track of the last value where mid * mid <= x as our best answer so far.

Step 4: Example – x = 10

Let’s see how this works for x = 10:

  1. low = 0, high = 10
  2. mid = 5 → 5 * 5 = 25 → too big → high = 4
  3. mid = 2 → 2 * 2 = 4 → too small → low = 3, answer = 2
  4. mid = 3 → 3 * 3 = 9 → still small → low = 4, answer = 3
  5. mid = 4 → 4 * 4 = 16 → too big → high = 3

Loop ends, and the last valid answer is 3.

Edge Cases

  • Perfect squares: For inputs like 25 or 100, the binary search will land exactly on the square root.
  • Non-perfect squares: For 10 or 99, the result will be the floor of the real square root.
  • Large numbers: Binary search handles even huge numbers like 1,000,000 efficiently in ~20 steps.
  • 0 or 1: Directly return the same number.
  • Negative numbers: There’s no real square root for negative inputs. We return -1 to indicate invalid input.
  • Invalid or empty input: If the input is null, undefined, or not a number, return -1.

Finally

This is a classic problem where binary search really shines. Instead of looping through all values up to x, we reduce the problem space by half in each iteration.

By understanding how square roots behave, and tracking midpoints smartly, we get a clean and efficient solution that works even for very large numbers — all in O(log x) time.

Algorithm Steps❯

  1. Set low = 0 and high = x.
  2. Initialize ans = -1 to keep track of closest answer.
  3. While low ≤ high, do:
  4. → Find mid = (low + high) / 2.
  5. → If mid * mid == x, return mid.
  6. → If mid * mid < x, update ans = mid, and move low = mid + 1.
  7. → Else, move high = mid - 1.
  8. Return ans.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int sqrtBinary(int x) {
    if (x == 0 || x == 1) return x;
    int start = 0, end = x, ans = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        long long square = (long long)mid * mid;

        if (square == x)
            return mid;
        else if (square < x) {
            ans = mid;
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return ans;
}

int main() {
    int x = 15;
    printf("Square root of %d is: %d\n", x, sqrtBinary(x));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)If the square root is found in the first mid calculation.
Average CaseO(log x)Binary search narrows down the possible square root range in logarithmic time.
Worst CaseO(log x)Search continues halving the range until low > high.

Space Complexity❯

O(1)

Explanation: No additional space is used; only constant variables are needed.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...