Efficiently Finding the Square Root of a Number: Linear Search vs Binary Search

Introduction

Finding the square root of a number is a common problem in mathematics and computer science. In this blog post, we will focus on the linear search and binary search methods for finding the square root of a number, and provide an implementation in C++ for each method.

Linear Search Method

The linear search method is a simple algorithm that iteratively checks each integer number from 1 to n to see if its square is equal to the input number n. If a number i is found such that i*i = n, then i is returned as the square root of n. If no such number is found, then the algorithm returns nothing.

Here is the implementation of the linear search method in C++:

1
2
3
4
5
6
7
8
int linear_search_mtd(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        if (i*i == n)
            return i;
    }
}

Binary Search Method

The binary search method is a more efficient algorithm for finding the square root of a number. It works by repeatedly dividing the search interval in half and checking if the middle number squared is equal to n. If the middle number squared is less than n, then the search interval is updated to the right half of the interval. Otherwise, the search interval is updated to the left half of the interval. This process continues until the square root of n is found.

Here is the implementation of the binary search method in C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_search_mtd(int n)
{
    int l = 1, r = n;

    while (l <= r)
    {
        int mid = (l+r)/2;

        if (mid*mid == n)
            return mid;
        else if (mid*mid < n)
            l = mid+1;
        else 
            r = mid-1;
    }
}

Comparison between Linear Search and Binary Search Methods

The binary search method is more efficient than the linear search method for finding the square root of a number. This is because the binary search method has a time complexity of O(log n), while the linear search method has a time complexity of O(n). In other words, the binary search method can find the square root of a number much faster than the linear search method, especially for large values of n.

If you’d like to see the complete code for checking prime numbers using an optimized algorithm, you can find it on my Github repository here.

Conclusion

In conclusion, finding the square root of a number is a common problem in mathematics and computer science. The linear search method and binary search method are two algorithms that can be used to solve this problem. The binary search method is more efficient than the linear search method, especially for large values of n. Both methods have been implemented in C++ and can be used depending on the specific requirements of the problem at hand.

If you’re interested in checking out some of my code related to algorithms and data structures, be sure to visit Algo-Data-Structure on Github. For my solutions to problems from competitive programming sites, you can find them in Competitive-Programming.

By the way, if you’re a teacher or parent looking for resources to help your child get ready for school, you might be interested in these fun and informative workbooks developed by a pre-school teacher. Covering all the basic skills needed for school-readiness, they’re perfect for the pre-school education niche. Check them out here: WORKSHEETS FOR PRESCHOOL