LeetCode: 69. Sqrt(x)

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

69. Sqrt(x)

LeetCode - Sqrt(x)

明知使用的是二分查找，竟然没有写出来！！

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:

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Runtime: 2 ms, faster than 14.88% of Java online submissions for Sqrt(x).
 *
 * Memory Usage: 34.1 MB, less than 5.00% of Java online submissions for Sqrt(x).
 *
 * Copy from: https://leetcode.com/problems/sqrtx/discuss/25047/A-Binary-Search-Solution[A Binary Search Solution - LeetCode Discuss]
 */
public int mySqrt(int x) {
    if (x == 0) {
        return 0;
    }
    int left = 1;
    int right = x;
    while (true) {
        int mid = left + (right - left) / 2;

        if (mid > x / mid) {
            right = mid - 1;
        } else {
            if (mid + 1 > x / (mid + 1)) {
                return mid;
            }
            left = mid + 1;
        }
    }
}