The “Square Root using Binary Search” problem is a classic question that helps you understand both brute force and binary search techniques. In this blog, we\u2019ll explain the problem, walk you through both brute force and binary search solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n You are given a non-negative integer Input:<\/strong> Output:<\/strong> Explanation:<\/strong> Input:<\/strong> Output:<\/strong> Explanation:<\/strong> Let\u2019s solve the problem in the most straightforward way:<\/p>\n\n\n\n This approach is easy to understand but not very efficient for large values of n.<\/p>\n\n\n\nWhat Does the Problem Say?<\/h2>\n\n\n\n
n<\/code>. Your task is to compute the floor value of the square root of n<\/code><\/strong> (i.e., the greatest integer x<\/code> such that x*x <= n<\/code>).<\/p>\n\n\n\nExample 1<\/h3>\n\n\n\n
n = 5<\/code><\/p>\n\n\n\n2<\/code><\/p>\n\n\n\n
The square root of 5 is approximately 2.236. The floor value is 2.<\/p>\n\n\n\nExample 2<\/h3>\n\n\n\n
n = 16<\/code><\/p>\n\n\n\n4<\/code><\/p>\n\n\n\n
The square root of 16 is exactly 4.<\/p>\n\n\n
\n\n\n\nBrute Force Solution (Linear Scan)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
Start from 0 and go up to n. For each number, check if its square is less than or equal to n.<\/li>\n\n\n\n
If the square is less than or equal to n, update the answer.<\/li>\n\n\n\n
As soon as the square of the number is greater than n, break the loop.<\/li>\n\n\n\n
We check every possible integer, so we\u2019re sure to find the largest integer whose square is less than or equal to n.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n