# 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.

## 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).

## 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.