Math Fundamentals18 sections · 814 units
Open in Course

Perfect Square - Binary Search

Finding the root

You can use binary search to find the square root. Search for an integer xx in the range [1,num][1, num] such that x2=numx^2 = num.

For each midpoint midmid, compute mid×midmid \times mid. If it equals numnum, you found it. If it's less, search the right half. If it's more, search the left half.

This runs in O(lognum)O(\log num) time because you halve the search space at each step. No square root function needed.