[leetcode]69. 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.

 

题意：

整数开方

Solution1： Binary Search

 

code

1 class Solution { 2 public int mySqrt(int x) { 3 if ( x == 0 ) return 0; 4 int left = 1; 5 int right = x; 6 int result = 0; 7 8 while (left <= right) { 9 int mid = left + (right - left) / 2; 10 if (mid <= x / mid) { 11 left = mid + 1; 12 result = mid; 13 } else { 14 right = mid - 1; 15 } 16 } 17 return result; 18 } 19 }

 

转载于:https://www.cnblogs.com/liuliu5151/p/10823266.html

相关资源：数据结构—成绩单生成器