代码随想录训练营Day57

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

提示：这里可以添加本文要记录的大概内容：

今天是跟着代码随想录刷题的第57天，继续复习数组的内容

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、X的平方根

思路：就是二分，重点注意可能会超时，所以不能用middle*middle<x,而是要middle<x/middle，然后把0和1的情况单独说
代码：

class Solution {
public:int mySqrt(int x) {if(x==0) return 0;if(x==1) return 1;int left=0;int right=x;while(left<=right){int middle=left+(right-left)/2;if(middle<x/middle){left=middle+1;}else if(middle==x/middle){return middle;}else{right=middle-1;}}return right;}
};

二、有效的完全平方数

思路：这道题注意要用long定义middle*middle因为可能会越界
代码：

class Solution {
public:bool isPerfectSquare(int num) {int left = 0, right = num;while (left <= right) {long mid = (right - left) / 2 + left;long square = mid * mid;if (square < num) {left = mid + 1;} else if (square > num) {right = mid - 1;} else {return true;}}return false;}
};