1 public class Solution {
 2     public int sqrt(int x) {
 3         if (x == 1 || x == 0) {
 4             return x;
 5         }
 6         
 7         int left = 1;
 8         int right = x;
 9         
10         while (left < right - 1) {
11             int mid = left + (right - left) / 2;
12             int quo = x / mid;
13             
14             if (quo == mid) {
15                 return quo;
16             // mid is too big    
17             } else if (quo < mid) {
18                 right = mid;
19             } else {
20                 left = mid;
21             }
22         }
23         
24         return left;
25     }
26 }