AcWing算法学习之二分法

简介: AcWing算法学习之二分法

系列文章目录

第一节:快速排序和归并排序

第二节:二分之整数二分和小数二分

@TOC


前言

第二节课我想给大家整理一下AcWing上边的二分系列的算法给大家.
二分本身就是数学的一种思想,列入数学的二分法求根的范围题目,到了编程这里就成为了一种思想算法,当然也不难,只要大家认真学习,今天就可以拿下这个知识点。


一、整数二分

我们先来说一下单调性和二分的区别,有单调性一定能进行二分排序,但是能进行二分排序的不一定有单调性。所以说二分的本质并非是单调性。
在这里插入图片描述

情况1.

我们假设有这样一个范围。我们能把它分成两个部分,左边不满足某一个条件,右面满足某一个条件。我们用二分法可以找到左边部分的边界和右边部分的边界。我们的红色部分和蓝色部分就是我们整数二分的两个不同的模板了。
在这里插入图片描述
我们来解释一下:

我们取中间值mid,如果mid在红色区域部分,我们通过条件去检查这个Mid发现它满足条件的话,那我们就把这个范围设定成mid到r的区域,如果mid不满足条件,那么就把范围设定在l到mid-1的区域。这样就把原来的区域一分为二了。

如果是这种情况我们来看一下这个模板:记得mid这里要加1

mid=(l+r+1)/2

这种情况是mid属于右面的是使用第二个模板:

**// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{

while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (check(mid)) l = mid;
    else r = mid - 1;
}
return l;

}**

情况2.

在这里插入图片描述
这种时候Mid在蓝色区域,满足条件就是1到Mid范围区间,反之是mid+1到r区间。

这地方确实我听课的时候没完全理解,这部分理解起来很难,所以可以找一个简便的方式去记下来,我们可以把mid在红色区域看成左边界,在蓝色区域看成是右边界,这样记的话,Mid在红色区域满足条件的范围是mid到r,在蓝色区域满足条件的范围是l到mid。

它的模板是:

**// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{

while (l < r)
{
    int mid = l + r >> 1;
    if (check(mid)) r = mid;    // check()判断mid是否满足性质
    else l = mid + 1;
}
return l;

}**

我们的条件是:
bool check(int x) {/ ... /} // 检查x是否满足某种性质

所以我们在做题的时候就是看区间是l=mid还是r=mid再来选取对应的模板。

我们现在来说一个问题就是在第一种情况时为什么Mid要加1的问题,因为当我们的l不巧正好等于r-1的时候,如果不加1,我们这里都是向下取整的,那Mid就还是l,那我们每次循环完,范围还是l到r就会发生死循环,如果我们加上1,那么就不一样了,mid就是r,我们最开始是l到r,经过一次循环的时候范围变成了r到r,就停止了。

二、小数二分

方法1---根据题目法

在这里插入图片描述
题目要求就是精确到小数点六位那我一般的做法是往后面多精确两位这样会使得我的结果更加准确.

这个重点是什么呢?当然是while循环里面的r-l>谁了,记住这一点啥也不用怕了就.

方法2迭代法

在这里插入图片描述
那就是for循环直接迭代一百次这样,emm看到这里其实会发现小数二分法很简单和固定.

三习题练习.

1.整数二分查找

在这里插入图片描述

#include<stdio.h>
int main()
{
    int n,q,arr[100010];
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&arr[i]);
    scanf("%d",&q);
again:
    while(q--)
    {
        int x;
        scanf("%d",&x);
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(arr[mid]>x) r=mid;
            else if(arr[mid]<x) l=mid+1;
            else
            {
                printf("YES\n");
                goto again;
            } 
            
        }
        if(arr[l]!=x) printf("NO\n");
    }
    return 0;
}

整数二分法简简单单做出来,其实就是套模板对不对?

2.数的范围在这里插入图片描述

#include<stdio.h>
int main()
{
    int n,q,arr[100010];
    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++) scanf("%d",&arr[i]);
    while(q--)
    {
        int x;
        scanf("%d",&x);
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=(r+l)/2;
            if(arr[mid]>=x) r=mid;
            else l=mid+1;
        }
        if(arr[l]!=x) printf("-1 -1\n");
        else 
        {
            printf("%d ",l);
            
            int l=0,r=n-1;
            while(l<r)
            {
                int mid=(r+l+1)/2;
                if(arr[mid]<=x) l=mid;
                else r=mid-1;
            }
            printf("%d \n",l);
        }
    }
    return 0;
}

套用模板就能写出来这个题目,是不是很轻松捏?

3.小数二分法

在这里插入图片描述

//写法一.
#include<stdio.h>
#include<math.h>
#include<string.h>
double sum(double x)
{
    return (x*x*x*x*x)-15*(x*x*x*x)+ 85*(x*x*x)- 225*(x*x)+ 274*x-121;
}
int main()
{
    double l=1.5,r=2.4,n,mid;
    while(fabs(r-l)>0.000000001)
    {
        mid=(l+r)/2;
        n=sum(mid);
        if(n>0)
        {
            l=mid;
        }
        else if(n<0)
        {
            r=mid;
        }
        else
        {
            break;
        }
    }
    printf("%.6lf",mid);
    return 0;
}
//写法二其实大同小异仅此而已.
#include<stdio.h>
double sum(double x)
{
    return (x*x*x*x*x)-15*(x*x*x*x)+ 85*(x*x*x)- 225*(x*x)+ 274*x-121;
}
int main()
{
    double l=1.5,r=2.4,n,mid;
    for(int i=0;i<100;i++)
    {
        mid=(l+r)/2;
        n=sum(mid);
        if(n>0) l=mid;
        else if(n<0) r=mid;
        else break;
    }
    printf("%.6lf",mid);
    return 0;
}

本质与总结.

二分的本质是边界:只要找到某种性质,使得整个区间一分为二,那么就可以用二分把边界点分出来
在这里插入图片描述
这个是我后面在acwing网站自己总结的一些思想,其实就是上边的汇总,大家可以就是学习一下。

总结自己对写题的看法:
**在你没学习二分之前你会觉得哇啊题目好难,但是如果你学了这些思想再去刷题是不是会事半功倍捏?所以在这里推荐一种学习思路给大家,就是先学而后可以练习学到的算法思想这样才会进步更快。
第二就是写一道题只给自己15min想思路的时间如果没想到就去看题解去总结学习题解,不然更多的时间只是浪费时间好吧,如果不赞同请写出你的方法蟹蟹!**

相关文章
|
1天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
17天前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
38 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
1天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
1天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
1天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!