Sqrt(x)

Problem

Implement int sqrt(int x).

Compute and return the square root of x.

Example

sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(10) = 3

Challenge

O(log(x))

Solutions

Binary Search.

Set low to 0 and high to x. In each iteration, calculate mid, if mid * mid is smaller than x, search in the higher half (from mid to high), else search in the lower half (from low to mid).

Binary Search is easy to understand but can be tricky to implement, pay attention to the conditions and make sure the code exits as expected.