實現 int sqrt(int x) 函數。
計算并返回 x 的平方根，其中 x 是非負整數。
由于返回類型是整數，結果只保留整數的部分，小數部分將被舍去。

示例 1:

輸入: 4
輸出: 2
示例 2:

輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842…,
由于返回類型是整數，小數部分將被舍去。

法一：暴力破解，直接從1開始計算平方，但暴力破解往往通不過。
法二：二分搜索
思路：mid平方<=x且（mid+1）平方>x時滿足題意，返回mid

class Solution { public:int mySqrt(int x) {//用二分搜索，當mid平方<=x且（mid+1）平方>x時滿足題意，返回midint left=1;int right=x;long mid=left+(right-left)/2;if(x == 0){return 0;}while(x/mid != mid){if(mid*mid > x){right=mid-1;mid=left+(right-left)/2;}else{if((mid + 1)*(mid + 1) > x){return mid;}else{left=mid+1;mid=left+(right-left)/2;}}}return mid;} };

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sqrtx
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的二分搜索之x平方根（保留整数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。