Square Root of Integer

Problem statement

Suppose we are given an integer a. Compute and return the square root of a. If a is not a perfect square, we will truncate the decimal digits.

Constraints:

• $0 \leq a \leq 10^3$

Example 1:

Input: 11    
Output: 3    

Explanation: The square root of 11 is 3.3166... and since the decimal part is truncated, 3 is returned.

Example 2:

Input: 9    
Output: 3    

Explanation: 9 gives a perfect square root.

Intuition

Binary search works well for searching elements in a sorted array. It works this way because the array itself is monotonic (either increasing or decreasing). Hence, if we are in a particular position, we can make a definite call as to whether the answer lies in the left part or the right part of the position.

A similar thing can be done with monotonic functions (monotonically increasing or decreasing) as well.
Let’s say there is a function $f(x)$, which increases when $x$ increases.

Hence, given a problem of finding $x$ so that $f(x) = v$, we can do a binary search for $x$ ...