leetcode 69，
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.
注意看代码里面的注释
class Solution { public int mySqrt(int x) { if (x<=1) return x; long left = 0; long right = x; while (left < right) { long mid = (left + right + 1)/2; if (mid * mid == x) { return (int)mid; } else if (mid * mid < x) {//关键就是当mid*mid < x的时候，mid可不可能成为结果，这道题里面答案显然是可能的， 但是对275来说就不是这样了， 因为必须是至少h个大于h的才行，所以应该用 mid = (left + right)/2 left = mid + 1; right = mid; left = mid; } else { right = mid - 1; } } return (int)(left); } }
二分模版
1. 开始对于特殊情况， len <= 1的情况做特殊处理。
2. 模版一 mid = (left + right)/2; left = mid + 1; right = mid; leetcode 275题， 模版二 mid = (left + right + 1)/2; left = mid; right = mid - 1; 应用于leetcode 69
3. 对于一定有解的情况直接返回即可， 如果可能没有结果的，最后一定要对left进行检验( 这个操作可能没用，但是不会有坏处 )
原文：https://www.cnblogs.com/tobemaster/p/10317773.html