Implement int sqrt(int x).

    Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

    Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

    Example 1:

    1. Input: 4
    2. Output: 2

    Example 2:

    1. Input: 8
    2. Output: 2
    3. Explanation: The square root of 8 is 2.82842..., and since 
    4.              the decimal part is truncated, 2 is returned.

    题意

    手动实现 int sqrt(int x)。

    思路

    二分法。

    代码实现

    1. class Solution {
    2.     public int mySqrt(int x) {
    3.         if (x == 0 || x == 1) {
    4.             return x;
    5.         }
    7.         // 对于大于等于2的值x，它的平方根小于等于x/2
    8.         int left = 1, right = x / 2;
    9.         while (left <= right) {
    10.             int mid = (left + right) / 2;
    11.             if (mid < x / mid) {
    12.                 left = mid + 1;
    13.             } else if (mid > x / mid) {
    14.                 right = mid - 1;
    15.             } else {
    16.                 return mid;
    17.             }
    18.         }
    20.         return left - 1;
    21.     }
    22. }