Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Input: 4Output: 2

Example 2:

Input: 8Output: 2Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.

class Solution {    public int mySqrt(int x) {//		long val = 0, tmp = 0;//		//		for (long i = 1; i <= x / 2 + 1; ++ i) {//			tmp = i * i;//			if (x == tmp) {//				val = i;//				break;//			}//			else if (x < tmp) {//				val = i - 1;//				break;//			}//		}//		//        return (int) val;				long tmp = 0, val = 0, rst = 0;		long head = 0, tail = x / 2 + 1;				while (head <= tail) {			tmp = (head + tail) / 2;			if ((val = tmp * tmp) == x) {				rst = tmp;				break;			}			else if (val < x) {				head = tmp + 1;			}			else {				tail = tmp - 1;				rst = tail;			}		}				return (int) rst;    }}