Valid Perfect Square: An Application of Binary Search Algorithm
What is a perfect square number? The answer is, the number which is made by squaring a whole number is called a perfect square. For example, 16 is a perfect square number because we can get 16 by squaring 4. Similarly, 25 is a perfect number because by squaring 5 we can get 25.
Now how can we check any given integer is a perfect square or not? What are the approaches to find that? Here you can find all of these answers.
We can easily check the valid perfect square of any positive integer within linear time or O(n) time complexity. But this approach could not find the solution in an optimal time for a very large positive integer. So, here we can apply the Binary Search algorithm to find a solution in optimal time, i.e. O(log n) time complexity.
Topics:
1) Linear time solution: O(n) time complexity
2) Optimal Solution: O(log n) time complexity
3) How O(n) and O(log n) differs
Linear Time Solution: O(n) time complexity
Suppose we want to check if 9 is a valid perfect square or not.
In the linear approach, we loop through 1 to 9 and try to find any number ‘i’ where ‘i’ times ‘i’ equals 9 i.e. i x i = 9. If this condition satisfies we can say that 9 is a valid perfect square. Here is the code of linear approach:
Now if we look again into this approach another thought may come to our mind that to check the valid perfect square of any positive integer N we need not loop through till N. It could be less than N and if we look closer than we can find that to check if N is valid perfect square we can loop through equal or less than N/2. So, we can optimize the above solution a bit here:
This 2nd approach is also not working for a very big positive integer.
Above both of the method gives O(n) or linear time solution for checking if any positive integer is a valid perfect square or not. This approach would fail to find a solution in an optimal time for very large N.
Optimal Solution: O(log n) time complexity
Here, we will see an optimal solution applying the Binary Search algorithm. Here is the code:
But if any positive integer does not fit in the ‘int’ type variable than this solution is not work for that number. So, we can use ‘long’ in place of ‘int’ in this code:
Now this solution will perfectly work for any positive integer.
How this approach checks if any positive integer number is a valid perfect square or not in O(log n) time is described here:
Suppose we want to check if 16 is a valid perfect square or not.
So, at iteration 1 we start our search from 2 to 8.
Formula for finding mid element is:
mid = lowPointer + ( (highPointer-lowPointer)/2 )
In this iteration, we find the mid element of the search space is 5.But 5 * 5 = 25 which is greater than 16. So, the square root of 16 must be less than 5. For this, we need to update highPointer position to point.
And the formula is: highPointer = mid-1 = 5–1 = 4
Now we are at 2nd iteration. Here, our search space contains a number from 2 to 4.
In this iteration, we find the mid element of the search space is 3. But 3 * 3 = 9 which is less than 16. So, the square root of 16 must be greater than 3. For this, we need to update lowPointer position to point.
And the formula is: lowPointer = mid+1 = 3+1 = 4
Now we are at 3rd iteration. Here search space contains only one element and that element is also the mid element.
Here, the mid element is 4 and 4*4 = 16. So, we find the square root of 16 which is 4 and it is a whole number. So 16 is a valid perfect square number.
Binary search will stop searching after this iteration because now lowPointer and highPointer both points to the same value and most importantly we find our result.
How time-complexity of this approach is O(log n) is described here:
See, we reach our result after 3rd iteration and at each iteration, we take half of the search space.
Initially, we 7 elements to search and we took half of it and goes on taking half at iteration till 1 element left. So, for finding the square root of 16 we have to take half of our search space 3 times.
Now assume we have to find the square root of n and so we need to take half of our search space k times. For that we can do this simple calculation:
How O(n) and O(log n) differs
Here, we can see O(n) graph increases linearly with the size of input where the increasing rate of O(log n) graph is much lower than O(n). So, any algorithm with O(log n) time complexity is much optimized than O(n).
Some Interesting Problems to be Solved using Binary Search
1) https://leetcode.com/problems/first-bad-version/
2) https://leetcode.com/problems/search-in-rotated-sorted-array/
3) https://leetcode.com/problems/valid-perfect-square/
And also many more binary-search related problems you can find in google search.
Thank you..!
Happy Coding..!
Reference: Binary-Search-Khan-Academy, Tutorialspoint-Binary-Search, Clever-Applications-of-Binary-Search
