Skip to main content

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.

  1. The binary search starts with a range of [start=1, last=37].
  2. The middle of this range is mid = (1 + 37) / 2 = 19.
  3. Check if mid * mid is equal to the input number (37 in this case).
  4. Since 19 * 19 is less than 37, the search range becomes [start=mid+1=20, last=37].
  5. The middle of the new range is mid = (20 + 37) / 2 = 28.
  6. Since 28 * 28 is greater than 37, the search range becomes [start=20, last=mid-1=27].
  7. The middle of this range is mid = (20 + 27) / 2 = 23.
  8. Since 23 * 23 is less than 37, the search range becomes [start=mid+1=24, last=27].
  9. The middle of this range is mid = (24 + 27) / 2 = 25.
  10. 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

  1. Start with the isPerfectSquare function that takes an integer num as input.
  2. If num is negative, return because negative numbers cannot have a perfect square.
  3. Initialize a variable result to store the result of the perfect square search.
  4. Call the findPerfectSquare function with num, start=1, and last=num as parameters.
  5. The findPerfectSquare function follows the binary search-based recursive approach: a. If start is greater than last, return 0 because the result does not exist. b. If start is equal to last, check if start * start is equal to num. If so, return start; otherwise, return 0. c. Calculate the middle value mid as (start + last) / 2. d. If mid * mid is equal to num, return mid as the perfect square. e. If mid * mid is less than num, update the search range to [start=mid+1, last] and make a recursive call. f. If mid * mid is greater than num, update the search range to [start, last=mid-1] and make a recursive call.
  6. Display the given number and the result of the perfect square search.

Code Solution

Here given code implementation process.

/*
    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).

Last updated on by Kalkicode




Comment

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