目录

69. x 的平方根

题目解析：

算法解析：

代码：

35. 搜索插入位置

题目解析：

算法解析：

代码：

69. x 的平方根

69. x 的平方根 - 力扣（LeetCode）

题目解析：

老规矩，先用暴力算法思考~

我们对从1到x的平方挨个遍历去寻找，如果发现遇到其平方和刚好相等那就返回原位置，如果x刚好卡在两数平方和之间，那就取其前面的。

算法解析：

我们通过暴力可以发现能将所有情况划分为两个区间，一个是平方和小于等于x，代表能得到结果的区间。另一个是平方和大于x的区间，代表无法得到结果的区间。

• 当mid*mid落入有结果区间时，left紧紧跟住mid即可。
• 当mid*mid落入无结果区间时，right跳出区间即可。

代码：

class Solution { public:     int mySqrt(int x) {         //特殊情况，特殊处理         if (x < 1) return 0;         int left = 1;         int right = x;         while (left < right)         {             //防止数值溢出             long long mid = left + (right - left + 1) / 2;             if (mid * mid > x)             {                 right = mid - 1;             }             else             {                 left = mid;             }         }         return left;     } };

35. 搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

题目解析：

这道题一看复杂度就知道要用二分查找了，而关键就在于我们需要找到其二段性。需要划分出有结果的区间与无结果的区间。

算法解析：

何为有结果区间呢？就比如我们找到与target相等的值就会返回其结果，找到比target大的值就意味要插入数组中并返回下标。这两个都是有结果的所以以它们为边界划分区间。

• 当mid落入有结果区间，left跟紧mid即可。
• 当mid落入无结果区间，right跳出区间即可。

代码：

class Solution { public:     int searchInsert(vector& nums, int target) {         int left = 0;         int right = nums.size() - 1;          while (left < right)         {             int mid = left + (right - left) / 2;              if (nums[mid] < target)             {                 left = mid + 1;             }             else             {                 right = mid;             }         }         if (nums[right] >= target)         {             return right;         }         //边界情况         else         {             return right + 1;         }     } };