69.Sqrt(x)

【题目】

Implementint sqrt(int x).

Compute and return the square root ofx, 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:

Input:
 4

Output:
 2

Example 2:

Input:
 8

Output:
 2

Explanation:
 The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

實現int sqrt（int x）函數。

計算並返回x的平方根，其中x是非負整數。

由於返回類型是整數，結果只保留整數的部分，小數部分將被捨去。

【思路】

二分法

【解法】

範例: x=4

先取中間值 (4/2)+1 = 3

H=3,L=0

(3+0)/2=1

1*1 != 4

在高點 H=3,L=0+1

(3+1)/2=2

2*2 == 4 Great!

☆JAVA

    public static int mySqrt(int x) {
    long high = (x / 2) + 1;
    long low = 0;
    while (high >= low) {
        long mid = (high + low) / 2;
        if (mid * mid == x)
            return (int)mid;
        else if (mid * mid > x)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return (int)high;
    }