二分查找图解
使用二分查找的前提是所给的元素集合必须是单调的。
注意：本文图文并茂
将提供以下图文链接供大家理解：
图文链接：
飞书图解链接🎉🎉🎉
密码：2k851&54
整数二分查找最后一个小于等于q的元素的下标
模板代码，展开查看
int last(int q){ int l = -1, r = n; while(l + 1 > 1; if(a[mid] <= q) l = mid; else r = mid; } return l;}元素存在
返回对应元素的下标
元素不存在
返回最大小于该元素的元素的下标
查找第一个大于等于q的元素的下标
模板代码，展开查看
int first(int q){ int l = -1, r = n; while(l + 1 > 1; if(a[mid] >= q) r = mid; else l = mid; } return r;}元素存在
返回对应元素的下标
元素不存在
返回最小大于该元素的元素的下标
习题一
AcWing 789. 数的范围
AC代码，展开查看
#includeusing namespace std;const int N = 1e5 + 10;int a[N];int n, m, q;int first(int q){ // 局部变量覆盖全局变量 int l = -1, r = n; while(l + 1 > 1; if(a[mid] >= q) r = mid; else l = mid; } return a[r] == q ? r : -1;}int last(int q){ // 局部变量覆盖全局变量 int l = -1, r = n; while(l + 1 > 1; if(a[mid] <= q) l = mid; else r = mid; } return a[l] == q ? l : -1;}int main(){ scanf("%d%d", &n, &m); for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]); while(m -- ){ scanf("%d", &q); printf("%d %d\n", first(q), last(q)); } return 0;}浮点数二分
最大化查找模板：
模板代码，展开查看
double find(double y){ double l = -22, r = 22; while(r - l > pre){ double mid = (l + r) / 2; if(mid * mid * mid <= y){ l = mid; }else{ r = mid; } } return l;}最小化查找模板：
模板代码，展开查看
double find(double y){ double l = -22, r = 22; while(r - l > pre){ double mid = (l + r) / 2; if(mid * mid * mid >= y){ r = mid; }else{ l = mid; } } return r;}习题一
AcWing 790. 数的三次方根
最大化AC代码，展开查看
#includeusing namespace std;const double pre = 1e-8;double find(double y){ double l = -22, r = 22; while(r - l > pre){ double mid = (l + r) / 2; if(mid * mid * mid > n; printf("%.6lf", find(n)); return 0;}最小化AC代码，展开查看
#includeusing namespace std;const double pre = 1e-8;double find(double y){ double l = -22, r = 22; while(r - l > pre){ double mid = (l + r) / 2; if(mid * mid * mid >= y){ r = mid; }else{ l = mid; } } return r;}int main(){ double n; cin >> n; printf("%.6lf", find(n)); return 0;}习题二
P2249 【深基13.例1】查找
AC代码，展开查看
#includeusing namespace std;const int N = 1e6 + 10;int a[N];int n, m, q;int first(int q){ // 局部变量覆盖全局变量 int l = -1, r = n; while(l + 1 > 1; if(a[mid] >= q) r = mid; else l = mid; } return a[r] == q ? r + 1 : -1;}int main(){ scanf("%d%d", &n, &m); for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]); while(m -- ){ scanf("%d", &q); printf("%d ", first(q)); } return 0;}习题三
P1024 [NOIP2001 提高组] 一元三次方程求解
AC代码，展开查看
#includeusing namespace std;const double pre = 1e-4;double a, b, c, d;double f(double x){ // 函数f(x) return a * x * x * x + b * x * x + c * x + d;}double find(double l, double r){ while(r - l > pre){ double mid = (l + r) / 2; if(f(mid) * f(r) > a >> b >> c >> d; for(int i = -100; i < 100; i ++ ){ double y1 = f(i), y2 = f(i + 1); // (-100, -99], (-99, -98], ..., (99, 100]: 排除根为100的情况 if(!y2) printf("%.2lf ", i + 1.0); // 有可能该点正好是根 if(y1 * y2 < 0) printf("%.2lf ", find(i, i + 1)); // 否则在(i, i + 1)区间二分根 } return 0;}高效的牛顿法
牛顿法（英语：Newton’s method）又称为牛顿-拉弗森方法（英语：Newton-Raphson method），它是一种在实数域和复数域上近似求解方程的方法。方法使用函数\(f(x)\)的泰勒级数的前面几项来寻找方程\(f(x)=0\)的根。
1. 方法说明
首先，选择一个接近函数\(f(x)\)零点的\(x_{0}\)，计算相应的\(f(x_0)\)和切线斜率\(f'(x_0)\)（这里\(f’\)表示函数\(f\)的导数）。然后我们计算穿过点\((x_{0},f(x_{0}))\)并且斜率为\(f'(x_0)\)的直线和\(x\)轴的交点的\(x\)坐标，也就是求如下方程的解：
$$
{\displaystyle 0=(x-x_{0})\cdot f'(x_{0})+f(x_{0})}
$$
我们将新求得的点的\(x\)坐标命名为\(x_1\)，通常\(x_1\)会比\(x_{0}\)更接近方程\(f(x)=0\)的解。因此我们现在可以利用\(x_1\)开始下一轮迭代。迭代公式可化简为如下所示：
$$
{\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}
$$
已有证明牛顿迭代法的二次收敛必须满足以下条件：
\(f'(x)\neq 0\); 对于所有\(x\in I\)，其中\({\displaystyle I}\)为区间\([α − r, α + r]\)，且\(x_{0}\)在区间其中\(I\)内，即 \(r\geqslant \left|a-x_{0}\right|\)的;
对于所有\({\displaystyle x\in I}\)，\(f”(x)\)是连续的;
\(x_{0}\)足够接近根 \(α\)。
2. 案例
第一个案例：
求方程\(\cos(x)-x^{3}=0\)的根。令\(f(x)=\cos(x)-x^{3}\)，两边求导，得\(f'(x)=-\sin(x)-3x^{2}\)。由于\(-1\leq \cos(x)\leq 1(\forall x)\)，则\(-1\leq x^{3}\leq 1\)，即\(-1\leq x\leq 1\)，可知方程的根位于\(0\)和\(1\)之间。我们从\({\displaystyle x_{0}=0.5}\)开始。
第二个案例：
牛顿法亦可发挥与泰勒展开式，对于函式展开的功能。
求\(a\)的\(m\)次方根。
\(x^{m}-a=0\)
设\(f(x)=x^{m}-a\)，\(f'(x)=mx^{m-1}\)
而\(a\)的\(m\)次方根，亦是\(x\)的解，
以牛顿法来迭代：
\[x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\]\[x_{n+1}=x_{n}-{\frac {x_{n}^{m}-a}{mx_{n}^{m-1}}}\]\[x_{n+1}=x_{n}-{\frac {x_{n}}{m}}{(1-ax_{n}^{-m})}\]
（或 $$x_{n+1}=x_{n}-{\frac {1}{m}}\left(x_{n}-a{\frac {x_{n}}{x_{n}^{m}}}\right)$$）
3. 应用
求解最值问题
牛顿法也被用于求函数的极值。由于函数取极值的点处的导数值为零，故可用牛顿法求导函数的零点，其迭代式为
\[x_{n+1}=x_{n}-{\frac {f^{\prime }(x_{n})}{f^{\prime \prime }(x_{n})}}\]
求拐点的公式以此类推
引例：
用牛顿法求解平方根：
如果要求\(S(S>1)\)的平方根，选取\(1 < x_{0} < S\)
\[x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {S}{x_{n}}}\right)\]
例子：求\(\sqrt {125348}\)至6位有效数字。
\[x_0 = 3^6 = 729.000\]\[x_1 = \frac{1}{2} \left(x_0 + \frac{S}{x_0}\right) = \frac{1}{2} \left(729.000 + \frac{125348}{729.000}\right) = 450.472\]\[x_2 = \frac{1}{2} \left(x_1 + \frac{S}{x_1}\right) = \frac{1}{2} \left(450.472 + \frac{125348}{450.472}\right) = 364.365\]\[x_3 = \frac{1}{2} \left(x_2 + \frac{S}{x_2}\right) = \frac{1}{2} \left(364.365 + \frac{125348}{364.365}\right) = 354.191\]\[x_4 = \frac{1}{2} \left(x_3 + \frac{S}{x_3}\right) = \frac{1}{2} \left(354.191 + \frac{125348}{354.191}\right) = 354.045\]\[x_5 = \frac{1}{2} \left(x_4 + \frac{S}{x_4}\right) = \frac{1}{2} \left(354.045 + \frac{125348}{354.045}\right) = 354.045\]
因此$$\sqrt{125348} \approx 354.045$$
代码实现：
package main import ( "fmt" ) func main() { // 求S = 125348的平方根 // 1. 选取1 < x0 < S // x0 = 3^6 = 729.00 // 2. 迭代5次 var S float64 = 125348 var x float64 = 729 for i := 0; i < 5; i ++ { x = 1 / 2.0 * (x + S / x) } fmt.Printf("x: %v\n", x) }结论:
不难看出
\[ x = \frac {1} {2} (x + \frac {S} {x})\]
等价于：
在数学上是等价的，在计算机上\(x^2\)会超过int所表示的范围，变成+Inf
\[ x = \frac {x^2 + S} {2x}\]
将\(x^2\)，变为\(2x^2 – x^2\)，然后化简得
\[x = x – \frac {x^2 – S} {2x}\]
我们来推导出这个公式：
设\(f(x) = x^2 – c \ (c \neq 0)\), \(f'(x) = 2x\), \(f”(x) = 2\)
证明二次收敛:
\(f'(x)\neq 0\); 对于所有\(x\in I\)，其中\({\displaystyle I}\)为区间\([1, c]\)，设近似根为\(x_0\)，且\(x_{0}\)在区间\(I\)内;
对于所有\({\displaystyle x\in I}\)，\(f”(x)\)是连续的;
\(x_{0}\)足够接近根 \(α\), \(α\)是实际的根。根据定义将\(x_0\)，代入
\[0=(x-x_{0})\cdot f'(x_{0})+f(x_{0})\]
- 因为二次收敛，所以等式两边除以\(f'(x_{0})\)，然后移项得
\[ x = x_0 – \frac {f(x_0)} {f'(x_0)}\]
- 则可以得到其迭代公式
\[ x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\]
- 代入求解得
\[ x_{n+1}=x_{n}-{\frac {x_n^2-c} {2x_{n}}}\]
推导完毕！
有了以上基础，下面就非常简单了
为了练习函数与循环，我们来实现一个平方根函数：用牛顿法实现平方根函数。
计算机通常使用循环来计算 \(x\) 的平方根。从某个猜测的值 \(z\) 开始，我们可以根据 \(z^2\) 与 \(x\) 的近似度来调整 \(z\)，产生一个更好的猜测：
\[z = z – \frac {z^2 – x} {2z}\]
重复调整的过程，猜测的结果会越来越精确，得到的答案也会尽可能接近实际的平方根。
在提供的 func Sqrt 中实现它。无论输入是什么，对 z 的一个恰当的猜测为 1。 要开始，请重复计算 10 次并随之打印每次的 z 值。
观察对于不同的值 \(x(1、2、3 …)\) ， 你得到的答案是如何逼近结果的，猜测提升的速度有多快。
提示：用类型转换或浮点数语法来声明并初始化一个浮点数值：
z := 1.0 z := float64(1)然后，修改循环条件，使得当值停止改变（或改变非常小）的时候退出循环。观察迭代次数大于还是小于 10。 尝试改变 z 的初始猜测，
如 x 或 x/2。你的函数结果与标准库中的 math.Sqrt 接近吗？
（注： 如果你对该算法的细节感兴趣，上面的 z² − x 是 z² 到它所要到达的值（即 x）的距离， 除以的 2z 为 z² 的导数，
我们通过 z² 的变化速度来改变 z 的调整量。 这种通用方法叫做牛顿法。 它对很多函数，特别是平方根而言非常有效。）
平方根函数
package main import ( "fmt" "math" ) func Sqrt(x float64) float64 { // z最好在 1 < z < 2 内取值 z := 1.5 // 迭代四次就够了 for i := 0; i < 4; i ++ { z -= (z * z - x) / (2 * z) fmt.Println(z) } return z } func main() { fmt.Println(Sqrt(2)) fmt.Println("================") fmt.Println(math.Sqrt(2)) }同理再实现一个立方根函数
package main import ( "fmt" ) func subtriplicate(x float64) float64 { z := 1.0 for i := 0; i < 10; i ++ { z = z - z / 3.0 + x / (3.0 * z * z); } return z } func main() { fmt.Printf("subtriplicate(7): %v\n", subtriplicate(7)) }总结：牛顿法收敛速度是二次方级别的，比二分法快多了
习题一
AcWing 790. 数的三次方根
AC代码，展开查看
#includeusing namespace std;double cube(double x){ double z = 1; for(int i = 0; i > x; printf("%.6lf", cube(x)); return 0;}本文参考自【董晓算法的个人空间-哔哩哔哩】
海纳百川，有容乃大！如果文章有什么不足之处，还请大神们评论区留言指出，我在此表达感谢🥰！若大家喜欢我的作品，欢迎点赞、收藏、打赏🎉🎉🎉！