二分查找图解

Posted on 2023年11月22日

二分查找图解

使用二分查找的前提是所给的元素集合必须是单调的。

注意：本文图文并茂

将提供以下图文链接供大家理解：
图文链接：
飞书图解链接🎉🎉🎉
密码：2k851&54

整数二分

查找最后一个小于等于q的元素的下标

模板代码，展开查看 
int last(int q){
    int l = -1, r = n;
    while(l + 1 > 1;
        if(a[mid]

元素存在
返回对应元素的下标
元素不存在
返回最大小于该元素的元素的下标

查找第一个大于等于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代码，展开查看 
#include
using 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]

浮点数二分

最大化查找模板：

模板代码，展开查看 
double find(double y){
    double l = -22, r = 22;
    while(r - l > pre){
        double mid = (l + r) / 2;
        if(mid * mid * mid

最小化查找模板：

模板代码，展开查看 
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代码，展开查看 
#include
using 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代码，展开查看 
#include
using 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代码，展开查看 
#include
using 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

习题三

P1024 [NOIP2001 提高组] 一元三次方程求解

AC代码，展开查看 
#include
using 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

高效的牛顿法

牛顿法（英语：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); 对于所有(xin I)，其中({displaystyle I})为区间([α − r, α + r])，且(x_{0})在区间其中(I)内，即 (rgeqslant left|a-x_{0}right|)的;
对于所有({displaystyle xin I})，(f”(x))是连续的;
(x_{0})足够接近根 (α)。

2. 案例

第一个案例：

求方程(cos(x)-x^{3}=0)的根。令(f(x)=cos(x)-x^{3})，两边求导，得(f'(x)=-sin(x)-3x^{2})。由于(-1leq cos(x)leq 1(forall x))，则(-1leq x^{3}leq 1)，即(-1leq xleq 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_{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

结论:
不难看出

[ 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}
]

我们来推导出这个公式：

  1. 设(f(x) = x^2 – c (c neq 0)), (f'(x) = 2x), (f”(x) = 2)

  2. 证明二次收敛:

    (f'(x)neq 0); 对于所有(xin I)，其中({displaystyle I})为区间([1, c])，设近似根为(x_0)，且(x_{0})在区间(I)内;
    对于所有({displaystyle xin I})，(f”(x))是连续的;
    (x_{0})足够接近根 (α), (α)是实际的根。

  3. 根据定义将(x_0)，代入

[0=(x-x_{0})cdot f'(x_{0})+f(x_{0})
]

  1. 因为二次收敛，所以等式两边除以(f'(x_{0}))，然后移项得
[ x = x_0 – frac {f(x_0)} {f'(x_0)}
]

  1. 则可以得到其迭代公式
[ x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}
]

  1. 代入求解得
[ 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

同理再实现一个立方根函数

  package main
  import (
    "fmt"
  )
  func subtriplicate(x float64) float64 {
    z := 1.0
    for i := 0; i

总结：牛顿法收敛速度是二次方级别的，比二分法快多了

习题一

AcWing 790. 数的三次方根

AC代码，展开查看 
#include
using namespace std;
double cube(double x){
    double z = 1;
    for(int i = 0; i > x;
    printf("%.6lf", cube(x));
    return 0;
}

本文参考自【董晓算法的个人空间-哔哩哔哩】

海纳百川，有容乃大！如果文章有什么不足之处，还请大神们评论区留言指出，我在此表达感谢🥰！若大家喜欢我的作品，欢迎点赞、收藏、打赏🎉🎉🎉！

机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net

相关文章：

  1. 河北廊坊服务器托管价格
  2. 高效稳定的服务器托管双线服务
  3. 重庆服务器托管信息服务器：稳定可靠的数据管理平台
  4. MCU，芯片杀价重灾区
  5. CLion Nova 强势登陆 C 和 C++ 开发领域，使用 ReSharper C++/Rider C++ 语言引擎！

机房租用，北京机房托管，大带宽租用，IDC机房租用托管服务器

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇:

©2023 机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 京ICP备13047091号