Posted on by Kalkicode
Code Recursion

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.

New Comment