69. Sqrt(x)

原题链接：https://leetcode.com/problems/sqrtx/description/
这道题目是让实现求一个平方根的约数，我的实现如下：

/**
 * Created by clearbug on 2018/2/26.
 */
public class Solution {

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.mySqrt(0));
        System.out.println(s.mySqrt(1));
        System.out.println(s.mySqrt(2));
        System.out.println(s.mySqrt(3));
        System.out.println(s.mySqrt(4));
        System.out.println(s.mySqrt(8));
        System.out.println(s.mySqrt(9));
        System.out.println(s.mySqrt(10));
        System.out.println(s.mySqrt(2147483647));
    }

    public int mySqrt(int x) {
        for (int i = 0; i < x; i++) {
            int curr = i * i;
            int largest = (i + 1) * (i + 1);

            if (largest < curr) { // 防止整形溢出
                return i;
            }

            if (curr == x) {
                return i;
            }
            if (largest == x) {
                return i + 1;
            }
            if (curr < x && largest > x) {
                return i;
            }
        }

        return 0;
    }

}

自认为代码还算简洁，思路还算清晰，但是 Submission Detail 却是：beats 3.73%！！！这让我很尴尬，那么怎么提高效率呢？随便看了下别人提交的答案，使用了类似二分查找的思想来提高效率，好吧，我们也来试试喽：

/**
 * Created by clearbug on 2018/2/26.
 */
public class Solution {

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.mySqrt(0));
        System.out.println(s.mySqrt(1));
        System.out.println(s.mySqrt(2));
        System.out.println(s.mySqrt(3));
        System.out.println(s.mySqrt(4));
        System.out.println(s.mySqrt(8));
        System.out.println(s.mySqrt(9));
        System.out.println(s.mySqrt(10));
        System.out.println(s.mySqrt(2147483647));
    }

    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }

        int start = 0;
        int end = x;
        while (start + 1 < end) {
            int middle = (start + end) / 2;

            if (middle < x / middle) {
                start = middle;
            } else if (middle > x / middle) {
                end = middle;
            } else {
                return middle;
            }
        }

        return start;
    }

}

可以看到，首先避免了整形移除的问题，然后使用二分查找思想加快了逼近结果的速度！