目录

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<int>& 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;}}
};