⬅ Previous Topic
Find Peak Element in ArrayNext Topic ⮕
Nth Root of a Number using Binary Search⬅ Previous Topic
Find Peak Element in ArrayNext Topic ⮕
Nth Root of a Number using Binary SearchTopic Contents
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).
low = 0
and high = x
.ans = -1
to keep track of closest answer.low ≤ high
, do:mid = (low + high) / 2
.mid * mid == x
, return mid
.mid * mid < x
, update ans = mid
, and move low = mid + 1
.high = mid - 1
.ans
.public class SqrtBinarySearch {
public static int sqrt(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 square = (long) mid * mid;
if (square == x)
return mid;
else if (square < x) {
ans = mid; // Store potential answer
start = mid + 1; // Look right for a closer higher sqrt
} else {
end = mid - 1; // Move left to reduce square
}
}
return ans;
}
public static void main(String[] args) {
int x = 15;
System.out.println("Square root of " + x + " is: " + sqrt(x));
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | If the square root is found in the first mid calculation. |
Average Case | O(log x) | Binary search narrows down the possible square root range in logarithmic time. |
Worst Case | O(log x) | Search continues halving the range until low > high. |
O(1)
Explanation: No additional space is used; only constant variables are needed.
⬅ Previous Topic
Find Peak Element in ArrayNext Topic ⮕
Nth Root of a Number using Binary SearchYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.