Find perfect square using binary search
The given problem is about finding a perfect square using binary search. A perfect square is a number that can be expressed as the square of an integer. For example, 4, 9, 16, 25, etc., are perfect squares because they can be represented as 2^2, 3^2, 4^2, 5^2, respectively.
The binary search algorithm is a searching technique that efficiently finds the target element in a sorted array by repeatedly dividing the search space in half. Applying binary search to find a perfect square of a given number can reduce the search time significantly.
Problem Statement
The task is to write a C program that takes an input number and finds its perfect square (if it exists) using a binary search-based recursive approach. If the perfect square is found, the program should display the square, otherwise, it should indicate that there is no perfect square for the given number.
Example
Let's consider an example with the input number 37.
- The binary search starts with a range of
[start=1, last=37]
. - The middle of this range is
mid = (1 + 37) / 2 = 19
. - Check if
mid * mid
is equal to the input number (37 in this case). - Since
19 * 19
is less than 37, the search range becomes[start=mid+1=20, last=37]
. - The middle of the new range is
mid = (20 + 37) / 2 = 28
. - Since
28 * 28
is greater than 37, the search range becomes[start=20, last=mid-1=27]
. - The middle of this range is
mid = (20 + 27) / 2 = 23
. - Since
23 * 23
is less than 37, the search range becomes[start=mid+1=24, last=27]
. - The middle of this range is
mid = (24 + 27) / 2 = 25
. - Since
25 * 25
is equal to 37, we have found the perfect square.
Pseudocode
function findPerfectSquare(num, start, last):
if start > last:
return 0
else if start == last:
if start * start == num:
return start
return 0
else:
mid = (start + last) / 2
if mid * mid == num:
return mid
else if mid * mid < num:
return findPerfectSquare(num, mid + 1, last)
else:
return findPerfectSquare(num, start, mid - 1)
Algorithm
- Start with the
isPerfectSquare
function that takes an integernum
as input. - If
num
is negative, return because negative numbers cannot have a perfect square. - Initialize a variable
result
to store the result of the perfect square search. - Call the
findPerfectSquare
function withnum
,start=1
, andlast=num
as parameters. - The
findPerfectSquare
function follows the binary search-based recursive approach: a. Ifstart
is greater thanlast
, return 0 because the result does not exist. b. Ifstart
is equal tolast
, check ifstart * start
is equal tonum
. If so, returnstart
; otherwise, return 0. c. Calculate the middle valuemid
as(start + last) / 2
. d. Ifmid * mid
is equal tonum
, returnmid
as the perfect square. e. Ifmid * mid
is less thannum
, update the search range to[start=mid+1, last]
and make a recursive call. f. Ifmid * mid
is greater thannum
, update the search range to[start, last=mid-1]
and make a recursive call. - Display the given number and the result of the perfect square search.
Code Solution
Here given code implementation process.
// C program for
// Find perfect square using binary search
#include <stdio.h>
// Find perfect square of given number using recursion
// and implemented by binary search
int findPerfectSquare(int num, int start, int last)
{
if (start > last)
{
// When result are not exist
return 0;
}
else if (start == last)
{
if (start *start == num)
{
return start;
}
return 0;
}
else
{
// Get the middle at the range from start to last
int mid = (start + last) / 2;
if (mid *mid == num)
{
// When mid is perfect square of given num
return mid;
}
if (mid *mid < num)
{
// Change the current range from mid+1 to last
return findPerfectSquare(num, mid + 1, last);
}
else
{
// Change the current range from start to last-1
return findPerfectSquare(num, start, last - 1);
}
}
}
// Handles the request to find perfect square of given num
void isPerfectSquare(int num)
{
if (num < 0)
{
// Because negative number cannot be a perfect square
return;
}
// Display given number
printf("\n Given number : %d", num);
int result = findPerfectSquare(num, 1, num);
if (result > 0)
{
printf("\n Perfect Square : (%d²)", result);
}
else
{
printf("\n Perfect Square : None");
}
}
int main(int argc, char
const *argv[])
{
// Test Cases
isPerfectSquare(9);
isPerfectSquare(196);
isPerfectSquare(37);
isPerfectSquare(324);
return 0;
}
input
Given number : 9
Perfect Square : (3²)
Given number : 196
Perfect Square : (14²)
Given number : 37
Perfect Square : None
Given number : 324
Perfect Square : (18²)
/*
Java Program
Find perfect square using binary search
*/
public class PerfectSquare
{
// Find perfect square of given number using recursion
// and implemented by binary search
public int findPerfectSquare(int num, int start, int last)
{
if (start > last)
{
// When result are not exist
return 0;
}
else if (start == last)
{
if (start * start == num)
{
return start;
}
return 0;
}
else
{
// Get the middle at the range from start to last
int mid = (start + last) / 2;
if (mid * mid == num)
{
// When mid is perfect square of given num
return mid;
}
if (mid * mid < num)
{
// Change the current range from mid+1 to last
return findPerfectSquare(num, mid + 1, last);
}
else
{
// Change the current range from start to last-1
return findPerfectSquare(num, start, last - 1);
}
}
}
// Handles the request to find perfect square of given num
public void isPerfectSquare(int num)
{
if (num < 0)
{
// Because negative number cannot be a perfect square
return;
}
// Display given number
System.out.print("\n Given number : " + num);
int result = findPerfectSquare(num, 1, num);
if (result > 0)
{
System.out.print("\n Perfect Square : (" + result + "²)");
}
else
{
System.out.print("\n Perfect Square : None");
}
}
public static void main(String[] args)
{
PerfectSquare task = new PerfectSquare();
// Test Cases
task.isPerfectSquare(9);
task.isPerfectSquare(196);
task.isPerfectSquare(37);
task.isPerfectSquare(324);
}
}
input
Given number : 9
Perfect Square : (3²)
Given number : 196
Perfect Square : (14²)
Given number : 37
Perfect Square : None
Given number : 324
Perfect Square : (18²)
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Find perfect square using binary search
*/
class PerfectSquare
{
public:
// Find perfect square of given number using recursion
// and implemented by binary search
int findPerfectSquare(int num, int start, int last)
{
if (start > last)
{
// When result are not exist
return 0;
}
else if (start == last)
{
if (start *start == num)
{
return start;
}
return 0;
}
else
{
// Get the middle at the range from start to last
int mid = (start + last) / 2;
if (mid *mid == num)
{
// When mid is perfect square of given num
return mid;
}
if (mid *mid < num)
{
// Change the current range from mid+1 to last
return this->findPerfectSquare(num, mid + 1, last);
}
else
{
// Change the current range from start to last-1
return this->findPerfectSquare(num, start, last - 1);
}
}
}
// Handles the request to find perfect square of given num
void isPerfectSquare(int num)
{
if (num < 0)
{
// Because negative number cannot be a perfect square
return;
}
// Display given number
cout << "\n Given number : " << num;
int result = this->findPerfectSquare(num, 1, num);
if (result > 0)
{
cout << "\n Perfect Square : (" << result << "²)";
}
else
{
cout << "\n Perfect Square : None";
}
}
};
int main()
{
PerfectSquare *task = new PerfectSquare();
// Test Cases
task->isPerfectSquare(9);
task->isPerfectSquare(196);
task->isPerfectSquare(37);
task->isPerfectSquare(324);
return 0;
}
input
Given number : 9
Perfect Square : (3²)
Given number : 196
Perfect Square : (14²)
Given number : 37
Perfect Square : None
Given number : 324
Perfect Square : (18²)
// Include namespace system
using System;
/*
Csharp Program
Find perfect square using binary search
*/
public class PerfectSquare
{
// Find perfect square of given number using recursion
// and implemented by binary search
public int findPerfectSquare(int num, int start, int last)
{
if (start > last)
{
// When result are not exist
return 0;
}
else if (start == last)
{
if (start * start == num)
{
return start;
}
return 0;
}
else
{
// Get the middle at the range from start to last
int mid = (start + last) / 2;
if (mid * mid == num)
{
// When mid is perfect square of given num
return mid;
}
if (mid * mid < num)
{
// Change the current range from mid+1 to last
return this.findPerfectSquare(num, mid + 1, last);
}
else
{
// Change the current range from start to last-1
return this.findPerfectSquare(num, start, last - 1);
}
}
}
// Handles the request to find perfect square of given num
public void isPerfectSquare(int num)
{
if (num < 0)
{
// Because negative number cannot be a perfect square
return;
}
// Display given number
Console.Write("\n Given number : " + num);
int result = this.findPerfectSquare(num, 1, num);
if (result > 0)
{
Console.Write("\n Perfect Square : (" + result + "²)");
}
else
{
Console.Write("\n Perfect Square : None");
}
}
public static void Main(String[] args)
{
PerfectSquare task = new PerfectSquare();
// Test Cases
task.isPerfectSquare(9);
task.isPerfectSquare(196);
task.isPerfectSquare(37);
task.isPerfectSquare(324);
}
}
input
Given number : 9
Perfect Square : (3²)
Given number : 196
Perfect Square : (14²)
Given number : 37
Perfect Square : None
Given number : 324
Perfect Square : (18²)
<?php
/*
Php Program
Find perfect square using binary search
*/
class PerfectSquare
{
// Find perfect square of given number using recursion
// and implemented by binary search
public function findPerfectSquare($num, $start, $last)
{
if ($start > $last)
{
// When result are not exist
return 0;
}
else if ($start == $last)
{
if ($start * $start == $num)
{
return $start;
}
return 0;
}
else
{
// Get the middle at the range from start to last
$mid = (int)(($start + $last) / 2);
if ($mid * $mid == $num)
{
// When mid is perfect square of given num
return $mid;
}
if ($mid * $mid < $num)
{
// Change the current range from mid+1 to last
return $this->findPerfectSquare($num, $mid + 1, $last);
}
else
{
// Change the current range from start to last-1
return $this->findPerfectSquare($num, $start, $last - 1);
}
}
}
// Handles the request to find perfect square of given num
public function isPerfectSquare($num)
{
if ($num < 0)
{
// Because negative number cannot be a perfect square
return;
}
// Display given number
echo("\n Given number : ".$num);
$result = $this->findPerfectSquare($num, 1, $num);
if ($result > 0)
{
echo("\n Perfect Square : (".$result.
"²)");
}
else
{
echo("\n Perfect Square : None");
}
}
}
function main()
{
$task = new PerfectSquare();
// Test Cases
$task->isPerfectSquare(9);
$task->isPerfectSquare(196);
$task->isPerfectSquare(37);
$task->isPerfectSquare(324);
}
main();
input
Given number : 9
Perfect Square : (3²)
Given number : 196
Perfect Square : (14²)
Given number : 37
Perfect Square : None
Given number : 324
Perfect Square : (18²)
/*
Node JS Program
Find perfect square using binary search
*/
class PerfectSquare
{
// Find perfect square of given number using recursion
// and implemented by binary search
findPerfectSquare(num, start, last)
{
if (start > last)
{
// When result are not exist
return 0;
}
else if (start == last)
{
if (start * start == num)
{
return start;
}
return 0;
}
else
{
// Get the middle at the range from start to last
var mid = parseInt((start + last) / 2);
if (mid * mid == num)
{
// When mid is perfect square of given num
return mid;
}
if (mid * mid < num)
{
// Change the current range from mid+1 to last
return this.findPerfectSquare(num, mid + 1, last);
}
else
{
// Change the current range from start to last-1
return this.findPerfectSquare(num, start, last - 1);
}
}
}
// Handles the request to find perfect square of given num
isPerfectSquare(num)
{
if (num < 0)
{
// Because negative number cannot be a perfect square
return;
}
// Display given number
process.stdout.write("\n Given number : " + num);
var result = this.findPerfectSquare(num, 1, num);
if (result > 0)
{
process.stdout.write("\n Perfect Square : (" + result + "²)");
}
else
{
process.stdout.write("\n Perfect Square : None");
}
}
}
function main()
{
var task = new PerfectSquare();
// Test Cases
task.isPerfectSquare(9);
task.isPerfectSquare(196);
task.isPerfectSquare(37);
task.isPerfectSquare(324);
}
main();
input
Given number : 9
Perfect Square : (3²)
Given number : 196
Perfect Square : (14²)
Given number : 37
Perfect Square : None
Given number : 324
Perfect Square : (18²)
# Python 3 Program
# Find perfect square using binary search
class PerfectSquare :
# Find perfect square of given number using recursion
# and implemented by binary search
def findPerfectSquare(self, num, start, last) :
if (start > last) :
# When result are not exist
return 0
elif (start == last) :
if (start * start == num) :
return start
return 0
else :
# Get the middle at the range from start to last
mid = int((start + last) / 2)
if (mid * mid == num) :
# When mid is perfect square of given num
return mid
if (mid * mid < num) :
# Change the current range from mid+1 to last
return self.findPerfectSquare(num, mid + 1, last)
else :
# Change the current range from start to last-1
return self.findPerfectSquare(num, start, last - 1)
# Handles the request to find perfect square of given num
def isPerfectSquare(self, num) :
if (num < 0) :
# Because negative number cannot be a perfect square
return
# Display given number
print("\n Given number : ", num, end = "")
result = self.findPerfectSquare(num, 1, num)
if (result > 0) :
print("\n Perfect Square : (", result ,"²)", end = "",sep = "")
else :
print("\n Perfect Square : None", end = "")
def main() :
task = PerfectSquare()
# Test Cases
task.isPerfectSquare(9)
task.isPerfectSquare(196)
task.isPerfectSquare(37)
task.isPerfectSquare(324)
if __name__ == "__main__": main()
input
Given number : 9
Perfect Square : (3²)
Given number : 196
Perfect Square : (14²)
Given number : 37
Perfect Square : None
Given number : 324
Perfect Square : (18²)
# Ruby Program
# Find perfect square using binary search
class PerfectSquare
# Find perfect square of given number using recursion
# and implemented by binary search
def findPerfectSquare(num, start, last)
if (start > last)
# When result are not exist
return 0
elsif (start == last)
if (start * start == num)
return start
end
return 0
else
# Get the middle at the range from start to last
mid = (start + last) / 2
if (mid * mid == num)
# When mid is perfect square of given num
return mid
end
if (mid * mid < num)
# Change the current range from mid+1 to last
return self.findPerfectSquare(num, mid + 1, last)
else
# Change the current range from start to last-1
return self.findPerfectSquare(num, start, last - 1)
end
end
end
# Handles the request to find perfect square of given num
def isPerfectSquare(num)
if (num < 0)
# Because negative number cannot be a perfect square
return
end
# Display given number
print("\n Given number : ", num)
result = self.findPerfectSquare(num, 1, num)
if (result > 0)
print("\n Perfect Square : (", result ,"²)")
else
print("\n Perfect Square : None")
end
end
end
def main()
task = PerfectSquare.new()
# Test Cases
task.isPerfectSquare(9)
task.isPerfectSquare(196)
task.isPerfectSquare(37)
task.isPerfectSquare(324)
end
main()
input
Given number : 9
Perfect Square : (3²)
Given number : 196
Perfect Square : (14²)
Given number : 37
Perfect Square : None
Given number : 324
Perfect Square : (18²)
/*
Scala Program
Find perfect square using binary search
*/
class PerfectSquare()
{
// Find perfect square of given number using recursion
// and implemented by binary search
def findPerfectSquare(num: Int, start: Int, last: Int): Int = {
if (start > last)
{
// When result are not exist
return 0;
}
else if (start == last)
{
if (start * start == num)
{
return start;
}
return 0;
}
else
{
// Get the middle at the range from start to last
var mid: Int = (start + last) / 2;
if (mid * mid == num)
{
// When mid is perfect square of given num
return mid;
}
if (mid * mid < num)
{
// Change the current range from mid+1 to last
return findPerfectSquare(num, mid + 1, last);
}
else
{
// Change the current range from start to last-1
return findPerfectSquare(num, start, last - 1);
}
}
}
// Handles the request to find perfect square of given num
def isPerfectSquare(num: Int): Unit = {
if (num < 0)
{
// Because negative number cannot be a perfect square
return;
}
// Display given number
print("\n Given number : " + num);
var result: Int = findPerfectSquare(num, 1, num);
if (result > 0)
{
print("\n Perfect Square : (" + result + "²)");
}
else
{
print("\n Perfect Square : None");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: PerfectSquare = new PerfectSquare();
// Test Cases
task.isPerfectSquare(9);
task.isPerfectSquare(196);
task.isPerfectSquare(37);
task.isPerfectSquare(324);
}
}
input
Given number : 9
Perfect Square : (3²)
Given number : 196
Perfect Square : (14²)
Given number : 37
Perfect Square : None
Given number : 324
Perfect Square : (18²)
/*
Swift 4 Program
Find perfect square using binary search
*/
class PerfectSquare
{
// Find perfect square of given number using recursion
// and implemented by binary search
func findPerfectSquare(_ num: Int, _ start: Int, _ last: Int) -> Int
{
if (start > last)
{
// When result are not exist
return 0;
}
else if (start == last)
{
if (start * start == num)
{
return start;
}
return 0;
}
else
{
// Get the middle at the range from start to last
let mid = (start + last) / 2;
if (mid * mid == num)
{
// When mid is perfect square of given num
return mid;
}
if (mid * mid < num)
{
// Change the current range from mid+1 to last
return self.findPerfectSquare(num, mid + 1, last);
}
else
{
// Change the current range from start to last-1
return self.findPerfectSquare(num, start, last - 1);
}
}
}
// Handles the request to find perfect square of given num
func isPerfectSquare(_ num: Int)
{
if (num < 0)
{
// Because negative number cannot be a perfect square
return;
}
// Display given number
print("\n Given number : ", num,terminator: "");
let result = self.findPerfectSquare(num, 1, num);
if (result > 0)
{
print("\n Perfect Square : (", result ,"²)",
separator: "", terminator: "");
}
else
{
print("\n Perfect Square : None", terminator: "");
}
}
}
func main()
{
let task = PerfectSquare();
// Test Cases
task.isPerfectSquare(9);
task.isPerfectSquare(196);
task.isPerfectSquare(37);
task.isPerfectSquare(324);
}
main();
input
Given number : 9
Perfect Square : (3²)
Given number : 196
Perfect Square : (14²)
Given number : 37
Perfect Square : None
Given number : 324
Perfect Square : (18²)
/*
Kotlin Program
Find perfect square using binary search
*/
class PerfectSquare
{
// Find perfect square of given number using recursion
// and implemented by binary search
fun findPerfectSquare(num: Int, start: Int, last: Int): Int
{
if (start > last)
{
// When result are not exist
return 0;
}
else if (start == last)
{
if (start * start == num)
{
return start;
}
return 0;
}
else
{
// Get the middle at the range from start to last
val mid: Int = (start + last) / 2;
if (mid * mid == num)
{
// When mid is perfect square of given num
return mid;
}
if (mid * mid < num)
{
// Change the current range from mid+1 to last
return this.findPerfectSquare(num, mid + 1, last);
}
else
{
// Change the current range from start to last-1
return this.findPerfectSquare(num, start, last - 1);
}
}
}
// Handles the request to find perfect square of given num
fun isPerfectSquare(num: Int): Unit
{
if (num < 0)
{
// Because negative number cannot be a perfect square
return;
}
// Display given number
print("\n Given number : " + num);
val result: Int = this.findPerfectSquare(num, 1, num);
if (result > 0)
{
print("\n Perfect Square : (" + result + "²)");
}
else
{
print("\n Perfect Square : None");
}
}
}
fun main(args: Array < String > ): Unit
{
val task: PerfectSquare = PerfectSquare();
// Test Cases
task.isPerfectSquare(9);
task.isPerfectSquare(196);
task.isPerfectSquare(37);
task.isPerfectSquare(324);
}
input
Given number : 9
Perfect Square : (3²)
Given number : 196
Perfect Square : (14²)
Given number : 37
Perfect Square : None
Given number : 324
Perfect Square : (18²)
Resultant Output
When running the given code with the test cases, we get the following output:
Given number : 9
Perfect Square : (3²)
Given number : 196
Perfect Square : (14²)
Given number : 37
Perfect Square : None
Given number : 324
Perfect Square : (18²)
Time Complexity
The time complexity of the binary search algorithm is O(log n), where n is the range of the search space (i.e.,
the given number in this case). In each recursion, the search space is halved. Hence, the time complexity of the
findPerfectSquare
function is O(log n).
The isPerfectSquare
function calls findPerfectSquare
, so its time complexity is also
O(log n).
Overall, the time complexity of the entire program is O(log n). The binary search approach makes it much faster than a linear search, which would have a time complexity of O(n).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment