“二分“==“二分查找“ ?“yes“:“no“;

不管现实多么惨不忍睹,都要持之以恒地相信,这只是黎明前短暂的黑暗而已。不要惶恐眼前的难关迈不过去,不要担心此刻的付出没有回报,别再花时间等待天降好运。真诚做人,努力做事!你想要的,岁月都会给你。“二分“==“二分查找“ ?“yes“:“no“;,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

在这里插入图片描述
                                                                   out.print( “二分”==“二分查找” ?“yes”:“no”);          


🌷 仰望天空,妳我亦是行人.✨
🦄 个人主页——微风撞见云的博客🎐
🐳 数据结构与算法专栏的文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺
🪁 希望本文能够给读者带来一定的帮助🌸文章粗浅,敬请批评指正!🐥


🍐二分的概念

我们通常说的二分一般分为:二分查找二分答案。那它们有什么区别呢?其实二分答案和二分查找都是二分法的应用,但它们的操作不同。

    🍊 二分查找:二分查找(Binary search)也称折半查找,是一种效率较高的查找方法。但是,二分查找要求线性表中的记录必须按关键码有序,并且必须采用顺序存储。

    🍊 二分答案:二分答案主要用于求解一个函数的最小值或最大值,通常是在一个确定的范围内(例如给定函数的定义域),通过不断二分缩小答案的范围,最终得到一个最优解或最优解的近似值。

🍏二分查找

时间复杂度

  • 二分查找最好时间复杂度是O(1),最好情况下只需要进行1次比较就能找到目标元素。
  • 二分查找最坏时间复杂度是:O(logn) ,最坏情况就是查找不到目标元素。
  • 二分查找平均时间复杂度是:O(logn)。

例如我们要查找26,那么从根节点开始,一次就能搜到,那么我们随机挑选一位幸运儿,假如我运气不好,选到了16,那我也只需要以O(logn)的时间复杂度,以 26 22 15 16 的顺序找到它。
在这里插入图片描述
递归实现二分查找:

public static int binarySearchRecursive(int[] arr, int key, int low, int high){
    if (low > high) {
        return -1;
    }
 
    int mid = (low + high)/2;
 
    if (key == arr[mid]) {
        return mid;
    } else if (key < arr[mid]) {
        return binarySearchRecursive(arr, key, low, mid-1);
    } else {
        return binarySearchRecursive(arr, key, mid+1, high);
    }
}

非递归二分查找:

下面是一个简单的非递归二分查找代码实现示例:

```java
public static int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

看了上述代码,你是否觉得太僵硬呆板?给你两个二分模板,保证嘎嘎上分!这里是找的其他大佬的板子,确实好用。 我们大多时候就是判断不好边界条件,导致写二分的时候耗时太长,分情况来模板化代码,有利于我们长期记忆和加深理解。)

模板1//第一个模板是尽量往左找目标  【只要是往左找答案,就用第一个模板,mid不用加一,r=mid,l加一;】
while (l < r){
    int mid = l + r >> 1;       //(l+r)/2
    if (check(mid))  r = mid;   // check()判断mid是否满足性质
    else l = mid + 1;
}

模板2//第二个模板是尽量往右找目标  【只要是往右找答案,就用第二个模板,mid要加一,l=mid,r要减一;】
while (l < r){
    int mid = l + r + 1 >> 1;   //(l+r+1)/2
    if (check(mid))  l = mid;
    else r = mid - 1;
}

🥑题目示例

题目:P2249 【深基13.例1】查找

题目描述

输入

n

n

n 个不超过

1

0

9

10^9

109 的单调不减的(就是后面的数字不小于前面的数字)非负整数

a

1

,

a

2

,

,

a

n

a_1,a_2,\dots,a_{n}

a1,a2,,an,然后进行

m

m

m 次询问。对于每次询问,给出一个整数

q

q

q,要求输出这个数字在序列中第一次出现的编号,如果没有找到的话输出

1

-1

1

输入格式

第一行

2

2

2 个整数

n

n

n

m

m

m,表示数字个数和询问次数。

第二行

n

n

n 个整数,表示这些待查询的数字。

第三行

m

m

m 个整数,表示询问这些数字的编号,从

1

1

1 开始编号。

输出格式

输出一行,

m

m

m 个整数,以空格隔开,表示答案。

样例 #1

样例输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

样例输出 #1

1 2 -1

提示

数据保证,

1

n

1

0

6

1 \leq n \leq 10^6

1n106

0

a

i

,

q

1

0

9

0 \leq a_i,q \leq 10^9

0ai,q109

1

m

1

0

5

1 \leq m \leq 10^5

1m105

本题输入输出量较大,请使用较快的 IO 方式。

🥑思路:区间是有单调性的,查找第一次出现的位置,如果查到一个值比目标值大,就把右半边放弃,因为右半边肯定也比目标值大;同样,如果查到值比目标值小,那就放弃左半边。

import java.io.*;

public class Main {
    static int N = (int) (1e6 + 10);
    static int[] a = new int[N];
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static void main(String[] args) throws IOException {
        int n = nextInt();
        int m = nextInt();
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        int l, r;
        while (m-- > 0) {
            int query = nextInt();
            l = 0;
            r = n;
            while (l < r) {
                int mid = l + r >> 1;
                if (query <= a[mid]) r = mid;//因为是要找第一次出现的位置,那么这个等于号是一定要加上的,因为我们是从右往左找的,等于的时候有可能前面还有
                else l = mid + 1;
            }
            if (a[r] == query)
                out.print(r + 1 + " ");//加一是因为问的序号而不是index
            else
                out.print(-1 + " ");
        }
        out.flush();
    }
}

题目:P1678 烦恼的高考志愿

题目背景

计算机竞赛小组的神牛 V 神终于结束了高考,然而作为班长的他还不能闲下来,班主任老 t 给了他一个艰巨的任务:帮同学找出最合理的大学填报方案。可是 v 神太忙了,身后还有一群小姑娘等着和他约会,于是他想到了同为计算机竞赛小组的你,请你帮他完成这个艰巨的任务。

题目描述

现有

m

m

m 所学校,每所学校预计分数线是

a

i

a_i

ai。有

n

n

n 位学生,估分分别为

b

i

b_i

bi

根据

n

n

n 位学生的估分情况,分别给每位学生推荐一所学校,要求学校的预计分数线和学生的估分相差最小(可高可低,毕竟是估分嘛),这个最小值为不满意度。求所有学生不满意度和的最小值。

输入格式

第一行读入两个整数

m

,

n

m,n

m,n

m

m

m 表示学校数,

n

n

n 表示学生数。

第二行共有

m

m

m 个数,表示

m

m

m 个学校的预计录取分数。第三行有

n

n

n 个数,表示

n

n

n 个学生的估分成绩。

输出格式

输出一行,为最小的不满度之和。

样例 #1

样例输入 #1

4 3
513 598 567 689
500 600 550

样例输出 #1

32

提示

数据范围:

对于

30

%

30\%

30% 的数据,

1

n

,

m

1000

1\leq n,m\leq1000

1n,m1000,估分和录取线

10000

\leq10000

10000

对于

100

%

100\%

100% 的数据,

1

n

,

m

100000

1\leq n,m\leq100000

1n,m100000,估分和录取线

1000000

\leq 1000000

1000000 且均为正整数。

🥑思路:要求估分和分数线相差最小,那肯定分数线刚超过估分或者估分刚超过分数线。我们就转化为,求第一个大于等于估分的分数线的位置。如此,这个位置的分数线或前一位置的分数线就是和估分相差最小的。

import java.io.*;
import java.util.Arrays;

public class Main {
    static int N = (int) (1e5 + 10);
    static int[] sch = new int[N];
    static int[] stu = new int[N];
    static int n, m, cnt;
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static void main(String[] args) throws IOException {
        n = nextInt();
        m = nextInt();
        for (int i = 0; i < n; i++) sch[i] = nextInt();
        Arrays.sort(sch, 0, n);
        for (int i = 0; i < m; i++) stu[i] = nextInt();
        //枚举学生
        //正确做法:从右往左走,走不动了的那个数就是我们需要的第一个大于等于自身的数
        for (int i = 0; i < m; i++) {
            int l = 0;
            int r = n;
            while (l < r) {
                int mid = l + r >> 1;
                if (sch[mid] >= stu[i]) r = mid;
                else l = mid + 1;
            }
            int abs1 = Integer.MAX_VALUE;
            int abs2 = Math.abs(stu[i] - sch[r]);
            if (r - 1 >= 0) abs1 = Math.abs(stu[i] - sch[r - 1]);
            cnt += Math.min(abs1, abs2);
        }
        out.println(cnt);
        out.flush();

        //错误做法:
        // 错误原因: 由于我们要找第一个比他大的,那就应该是从右往左走,
        // 继续走的条件是大于等于它,如果不能继续走就说明我们已经到达了第一个点,而不是去找最后一个不符合条件的
        /*for (int i = 0; i < m; i++) {
            //找出第一个学校分数线大于等于它的
            //(注意:这里实际上找的是满足条件的前一个,因为我们的条件是不满足,所以退出的时候,返回的是最后一个不满足的值,满足的值在下一个)
            int l = 0;
            int r = n;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (stu[i] > sch[mid]) l = mid;
                else r = mid - 1;
            }
            //比较当前分数线和前一个分数线与学生分数作差的abs大小
            int abs1 = Integer.MAX_VALUE;
            int abs2 = Integer.MAX_VALUE;
            abs1 = Math.abs(stu[i] - sch[r]);
            if (r + 1 < n) abs2 = Math.abs(stu[i] - sch[r + 1]);
            if (abs1 != Integer.MAX_VALUE && abs2 != Integer.MAX_VALUE)
            cnt += Math.min(abs1, abs2);
        }*/
    }
}


🍏二分答案

如何判断一个题是不是用二分答案做的呢?

  1. 答案在一个区间内(一般情况下,区间会很大,暴力超时)
  2. 直接搜索不好搜,但是容易判断一个答案可行不可行
  3. 该区间对题目具有单调性,即:在区间中的值越大或越小,题目中的某个量对应增加或减少。

此外,可能还会有一个典型的特征 求...最大值的最小求...最小值的最大
1、求...最大值的最小,我们二分答案(即二分最大值)的时候,判断条件满足后,尽量让答案往前来(即:让r=mid),对应模板1
2、求...最小值的最大时,我们二分答案(即二分最小值)的时候,判断条件满足后,尽量让答案往后走(即:让l=mid),对应模板2


题目:P2678 [NOIP2015 提高组] 跳石头

题目背景

一年一度的“跳石头”比赛又要开始了!

题目描述

这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有

N

N

N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走

M

M

M 块岩石(不能移走起点和终点的岩石)。

输入格式

第一行包含三个整数

L

,

N

,

M

L,N,M

L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。保证

L

1

L \geq 1

L1

N

M

0

N \geq M \geq 0

NM0

接下来

N

N

N 行,每行一个整数,第

i

i

i 行的整数

D

i

(

0

<

D

i

<

L

)

D_i( 0 < D_i < L)

Di(0<Di<L), 表示第

i

i

i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。

输出格式

一个整数,即最短跳跃距离的最大值。

样例 #1

样例输入 #1

25 5 2 
2
11
14
17 
21

样例输出 #1

4

提示

输入输出样例 1 说明

将与起点距离为

2

2

2

14

14

14 的两个岩石移走后,最短的跳跃距离为

4

4

4(从与起点距离

17

17

17 的岩石跳到距离

21

21

21 的岩石,或者从距离

21

21

21 的岩石跳到终点)。

数据规模与约定

对于

20

%

20\%

20%的数据,

0

M

N

10

0 \le M \le N \le 10

0MN10
对于

50

%

50\%

50% 的数据,

0

M

N

100

0 \le M \le N \le 100

0MN100
对于

100

%

100\%

100%的数据,

0

M

N

50000

,

1

L

1

0

9

0 \le M \le N \le 50000,1 \le L \le 10^9

0MN50000,1L109

🥑思路:求最大?–> 模板2;(代码有注释)
我们二分的是最短距离,通过二分将这个最短距离(答案)最大化。如果能搬走的石头没超过规定的数量,那么我们还能继续尝试把答案开得更大一些。否则的话就说明我们开的长度太大了,要缩小一点。

import java.io.*;

public class Main {
    static int N = (int) 5e4 + 10;
    static int len, n, m;
    static int[] a = new int[N];//每块岩石与起点的距离 从小到大
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws IOException {
        len = nextInt();
        n = nextInt();
        m = nextInt();
        for (int i = 0; i < n; i++) a[i] = nextInt();
        int l = 0;
        int r = len;
        while (l < r) {
            int mid = l + r + 1 >> 1;//mid为答案
            if (check(mid)) l = mid;//如果能搬走的石头没超过规定的数量,那么我们还能继续尝试把答案开得更大一些。
            else r = mid - 1;//否则的话就说明我们开的长度太大了,要缩小一点
        }
        System.out.println(r);
    }

    static boolean check(int mid) {
        int cnt = 0;//记录搬走了多少块岩石
        int position = 0;//记录当前位置
        for (int i = 0; i < n; i++) {
            if (a[i] - position < mid) cnt++;//如果从当前位置到岩石的位置长度小于mid则搬走,因为我们要找最大的最短跳跃长度
            else position = a[i];//同理,如果从当前位置到岩石的位置长度比我们当前的答案大,那么我们就把当前岩石当作新的起点继续找下去。
        }
        return cnt <= m;//没超出则返回true
    }

    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }


}


题目:P1182 数列分段 Section II

题目描述

对于给定的一个长度为N的正整数数列

A

1

N

A_{1\sim N}

A1N,现要将其分成

M

M

M

M

N

M\leq N

MN)段,并要求每段连续,且每段和的最大值最小。

关于最大值最小:

例如一数列

4

 

2

 

4

 

5

 

1

4\ 2\ 4\ 5\ 1

4 2 4 5 1 要分成

3

3

3 段。

将其如下分段:

[

4

 

2

]

[

4

 

5

]

[

1

]

[4\ 2][4\ 5][1]

[4 2][4 5][1]

第一段和为

6

6

6,第

2

2

2 段和为

9

9

9,第

3

3

3 段和为

1

1

1,和最大值为

9

9

9

将其如下分段:

[

4

]

[

2

 

4

]

[

5

 

1

]

[4][2\ 4][5\ 1]

[4][2 4][5 1]

第一段和为

4

4

4,第

2

2

2 段和为

6

6

6,第

3

3

3 段和为

6

6

6,和最大值为

6

6

6

并且无论如何分段,最大值不会小于

6

6

6

所以可以得到要将数列

4

 

2

 

4

 

5

 

1

4\ 2\ 4\ 5\ 1

4 2 4 5 1 要分成

3

3

3 段,每段和的最大值最小为

6

6

6

输入格式

1

1

1 行包含两个正整数

N

,

M

N,M

N,M

2

2

2 行包含

N

N

N 个空格隔开的非负整数

A

i

A_i

Ai,含义如题目所述。

输出格式

一个正整数,即每段和最大值最小为多少。

样例 #1

样例输入 #1

5 3
4 2 4 5 1

样例输出 #1

6

提示

对于

20

%

20\%

20% 的数据,

N

10

N\leq 10

N10

对于

40

%

40\%

40% 的数据,

N

1000

N\leq 1000

N1000

对于

100

%

100\%

100% 的数据,

1

N

1

0

5

1\leq N\leq 10^5

1N105

M

N

M\leq N

MN

A

i

<

1

0

8

A_i < 10^8

Ai<108, 答案不超过

1

0

9

10^9

109

🥑思路:求最小值? –> 模板1;
判断条件:要保证:每一段的和都小于等于最大值。也就是说,只要这一段的和加上下一个值大于最大值了,那下一个值加不得,得分段!接着段数++;
我们从第一个开始,把它自己当做一段,并且我们的左边界应该是数组里面最大的值(最大值至少也是自成一段),而右边界是全部数组数值相加(最大值最大就是全部加起来)。

import java.io.*;

public class Main {
    static int N = (int) 1e5 + 10;
    static long n, m, l, r;
    static long[] a = new long[N];
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws IOException {
        n = nextLong();
        m = nextLong();
        for (int i = 0; i < n; i++) {
            a[i] = nextLong();
            l = Math.max(l, a[i]);
            r += a[i];
        }
        while (l < r) {
            long mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        System.out.println(r);
    }

    static boolean check(long mid) {
        long cnt = 1;
        long sum = a[0];
        for (int i = 1; i < n; i++) {
            if (sum + a[i] > mid) {
                cnt++;
                sum = a[i];
            } else sum += a[i];
        }
        return cnt <= m;
    }

    static long nextLong() throws IOException {
        in.nextToken();
        return (long) in.nval;
    }


}

看完之后是不是对二分有了更深入的理解呢? (* ̄︶ ̄)❀

在这里插入图片描述


🐳结语

🐬初学一门技术时,总有些许的疑惑,别怕,它们是我们学习路上的点点繁星,帮助我们不断成长。

🐟文章部分语录摘自以下博文,因为其中的部分语录十分容易理解。 希望对大家有帮助!

🦄参考文章二分查找 & 二分答案 万字详解,超多例题,带你学透二分。查找算法:二分查找

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/159802.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!