阅读量:0
目录
69. x 的平方根
题目解析：
老规矩，先用暴力算法思考~
我们对从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. 搜索插入位置
题目解析：
这道题一看复杂度就知道要用二分查找了，而关键就在于我们需要找到其二段性。需要划分出有结果的区间与无结果的区间。
算法解析：
何为有结果区间呢？就比如我们找到与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; } } };