建设网站上传软件,重庆农产品价格信息网,wordpress添加面包屑导航,深圳网站-建设信科网络二分法前言69. x 的平方根35. 搜索插入位置前言
二分查找也常被称为二分法或者折半查找#xff0c;每次查找时通过将待查找区间分成两部分并只取一部分继续查找#xff0c;将查找的复杂度大大减少。对于一个长度为 O(n) 的数组#xff0c;二分查找的时间复杂度为 O(log n)。…
二分法前言69. x 的平方根35. 搜索插入位置前言
二分查找也常被称为二分法或者折半查找每次查找时通过将待查找区间分成两部分并只取一部分继续查找将查找的复杂度大大减少。对于一个长度为 O(n) 的数组二分查找的时间复杂度为 O(log n)。
69. x 的平方根 题解 我们可以把这道题想象成给定一个非负整数 aaa求f(x)x2,a0f (x) x2,a 0f(x)x2,a0 的解。因为我们只考虑 x≥0x ≥ 0x≥0所以 f(x)f (x)f(x) 在定义域上是单调递增的。考虑到 f(0)a≤0f(a)a2a≥0f (0) a ≤ 0 f (a) a2 a ≥ 0f(0)a≤0f(a)a2a≥0我们可以对 [0,a][0, a][0,a] 区间使用二分法找到 f(x)0f (x) 0f(x)0 的解。
代码
class Solution {
public:int mySqrt(int x) {if(x 1)return 1;int min 0;int max x;while(max-min1){int m (maxmin)/2;if(x/mm)max m;elsemin m;}return min;}
};
35. 搜索插入位置 题解 例如到底是 while(leftright)while(left right)while(leftright) 还是 while(leftright)while(left right)while(leftright)到底是rightmiddleright middlerightmiddle呢还是要rightmiddle−1right middle- 1rightmiddle−1呢
这里弄不清楚主要是因为**「对区间的定义没有想清楚这就是不变量」**。
要在二分查找的过程中保持不变量这也就是**「循环不变量」**。
代码
class Solution {
public:int searchInsert(vectorint nums, int target) {int n nums.size();int left 0;int right n - 1; // 定义target在左闭右闭的区间里[left, right] while (left right) { // 当leftright区间[left, right]依然有效int middle left ((right - left) / 2);// 防止溢出 等同于(left right)/2if (nums[middle] target) {right middle - 1; // target 在左区间所以[left, middle - 1]} else if (nums[middle] target) {left middle 1; // target 在右区间所以[middle 1, right]} else { // nums[middle] targetreturn middle;}}// 分别处理如下四种情况// 目标值在数组所有元素之前 [0, -1]// 目标值等于数组中某一个元素 return middle;// 目标值插入数组中的位置 [left, right]return right 1// 目标值在数组所有元素之后的情况 [left, right] return right 1return right 1;}
};
