快速排序

快速排序的主要思想是基于分治

  1. ==确定分界点==:q[l], q[r], q[(l + r )/ 2], q[随机]
  2. ==调整区间==: 把整个区间通过x的值划分成两部分,这两部分的长度不一定相等,使得第一个区间里面的所有数都<=x,第二个区间里面的所有数都>=x.注意x不一定在两个区间的交界处.(如果和x相等的话,可能在x左边,也可能在x右边,所以前面的表述都是<=和>=)
  3. ==递归处理左,右两段==.只要左边排好顺序,右边排好顺序,那么左右两边拼到一块形成的整个就是拍好序了.(因为左边的最大值是<=右边的最小值)

2.调整区间是最难的地方,有很多种实现方法.

方法一

  1. 开两个额外的数组a[] 和 b[]

  2. 扫描q[l —- r].如果当前数<=x,就把它查到a[]里面去;如果当前数>x,就把它查到b[]里面去;

  3. 先把a[]放到q[]里面去,再把b[]放到q[]里面去.(这个时候a[]里面所有数都<=x,b[]里面所有数都>x,已经满足上面的性质了)

    这是暴力做法,时间复杂度O(n),空间复杂度高,因为要开两个额外的数组空间.

方法二

双指针i指向最左边,j指向最右边

i向中间走,找到第一个>=x的数,然后就不用动;j向中间走,找到第一个<=x的数,此时把i和j指向的数swap;这样子i,j一直往中间走,知道i, j相遇为止.这样之后就能把区间一分为二了.

785快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
using namespace std;
const int N = 1e6 + 10	;//一后面6个零,应该是1e6 + 10
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    // 注意快速排序这道题目的数据已加强，划分中点取左端点或右端点时会超时，改成取中点或者随机值即可。
    //  每次交换玩指针都要往中间移动一格,
    //  因此后面循环是这样做的,
    //  每次不管三七二十一,
    //  先把指针往中间移动一格,
    //  然后再去判断,因此两个指针都要放在左右两个边界的左右一格,
    //  这样我们往中间移动一格之后才是真正的边界
    //  所以才有一个偏移量,需要往两边扩一格
    //  int x = q[(l + r) / 2];
    //  int x = q[r];
    while (i < j)
    {
        do
            i++;
        while (q[i] < x);
        do
            j--;
        while (x < q[j]);
        if (i < j)
            swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", q[i]);
    return 0;
}

第一步是判断边界,如果区间里面只有一个数或者没有数的话,我们就直接return;事实上也就是递归结束的条件.

第二步是while(i < j)循环执行,每一次i,j移动和swap(q[i], q[j])算一次.

找到第一个令q[i] >= x的i,找到第一个令q[j] <= x的j,两个指针只要没有相遇(就是i >= j)的话,就交换(所以才会在swap前面加一个if语句,如果i >=j,i和j相遇了,那就不swap,同时交给下一轮的while(i<j) 来退出循环)

如果你的语言里面没有swap函数,就用

1
2
3
4
5
if(i < j){
int t  = q[i] ;
q[i]  = q[j] ;
q[j] = t ;
}

为什么边界写成下面这样呢?

1
2
quick_sort(q, l, j);
quick_sort(q, j + 1 , r);

图示:

红剪头是指针i,绿箭头是指针j

image-20241103084313121

while(i < j)这个循环结束时候,i肯定是>=j的,同时i(不包括i)的前面都是<=x的数,同时j(不包括j)的后面都是=>x的数

(根据这个结束的状态我个人认为可以判断while(i < j) 循环结束时只有两种情况:一是i == j,二是 i > j,更加具体的说,二是i > j的i和j 的中间都是等于x 的数,因此你用

1
2
quick_sort(q, l, j);
quick_sort(q, j + 1, r);

或者

1
2
quick_sort(q, l, i - 1);
quick_sort(q, i, r);

无非是i和j中间可能存在的若干个和x相同的数划分到左区间还是右区间的问题,但是无论是左区间还是右区间,都在左区间的最右段,右区间的最左段.还是不影响快排的正确性.

).可以见下面的图;

红剪头是指针i,绿箭头是指针j

不包括i指针前面所有的数都是<=x的,不包括j指针后面所有的数都是>=x的

image-20241103090100453

所以根据这个图示,边界是这样的.

1
2
quick_sort(q, l, j);
quick_sort(q, j + 1, r);

下面这段可以把j换成i,只要满足对称就行了,根据图示来

1
2
quick_sort(q, l, i - 1);
quick_sort(q, i, r);

==但用i的话绝对不能写成int x = q[l]==,会有边界问题,用int x = q[r]或者int x = q[(l + r + 1) / 2],要向上取整,一定不能取到l这个边界上面.不然会有边界问题,会有死循环.

(举个具体的例子

对于 n = 2, 输入的数字为 1 2这种情况来说,就会死循环

while(i < j)结束时,i = 0, j = 0

quick_sort(q, l, i - 1); 就是 quick_sort(q, 0, - 1);直接return返回
quick_sort(q, i, r);就是quick_sort(q, 0, 1);进入一样的循环,所以死循环.

)

==同理用 j 的话,一定不能写成int x = q[r]==

事实上,不用你都每一个都非常熟悉,,只要你会常用的经典没错的模板就行了.

==反正可以对着记忆用j就是q[l], q[(l + r )/ 2], q[随机] ,==

==(目前来看用j 的话q[(l + r )/ 2]run正确,q[(l + r + 1)/ 2]run错误)==

==用i 的话就是int x = q[r]或者int x = q[(l + r + 1) / 2],==

七次

1103第一次

第二遍写的时候,漏掉了scanf(“%d”, &n)里面的&

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    while (i < j)
    {
        do
            i++;
        while (q[i] < x);
        do
            j--;
        while (x < q[j]);
        if (i < j)
            swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}
int main(void)
{
    scanf("%d", n);//错误
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}

1104第二次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N];
void quick_sort(int q[], int l, int r);

int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
        printf("%d ", q[i]);
    return 0;
}
void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return; // 这是一个疑点,我认为是l >= r 的原因是当l == r的时候一个元素组成的序列就是有序的,所以你不用再递归下去了,这就是最后一层递归了,直接返回上一层就行
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    // 个人记忆口诀,快排和归并排序都用到i和j来对数组q[] 的当下这一层递归的部分 也就是l 到 r这一部分进行处理
    // 同时不能改变l 和 r的值,因为要作为实参传给下一层递归,所以用借用i和j
    // 二分查找就不需要i和j,因为直接在while循环里面更新l = mid或者 r = mid来让区间缩小
    while (i < j)
    { // 个人记忆口诀,对于快拍而言,因为这个while循环条件是i < j,所以递归终止条件是if (i >= j)
        do
            i++;
        while (q[i] < x);
        do
            j--;
        while (q[j] > x);
        if (i < j)
            // 不能忘了这个if,因为很可能你找到i和j后就已经不满足i < j的条件了,
            // 我记得y总一开始举的数组序列的例子就是第一次找到的i和j之后,发现i >= j了
            swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

疑点1

1
2
if (l >= r)
    return; // 这是一个疑点,我认为是l >= r 的原因是当l == r的时候一个元素组成的序列就是有序的,所以你不用再递归下去了,这就是最后一层递归了,直接返回上一层就行

查找第一次写的代码就是if(l >= r),个人认为的原因就是我上面的注释

疑点2

1
2
3
4
5
6
int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    // 个人记忆口诀,快排和归并排序都用到i和j来对数组q[] 的当下这一层递归的部分 也就是l 到 r这一部分进行处理
    // 同时不能改变l 和 r的值,因为要作为实参传给下一层递归,所以用借用i和j
    // 二分查找就不需要i和j,因为直接在while循环里面更新l = mid或者 r = mid来让区间缩小
    while (i < j)
    { // 个人记忆口诀,对于快拍而言,因为这个while循环条件是i < j,所以递归终止条件是if (i >= j)

疑点3

1
2
3
4
if (i < j)
            // 不能忘了这个if,因为很可能你找到i和j后就已经不满足i < j的条件了,
            // 我记得y总一开始举的数组序列的例子就是第一次找到的i和j之后,发现i >= j了
            swap(q[i], q[j]);

疑点4

我要验证一波最后的情况

用j的时候

1
2
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
1
int x = q[(l + r) / 2]

结果正确

1
int x = q[l]

y总run的时候是正确的,我run的时候数据加强了,所以超时了,Time Limit Exceeded

但是并不是Memory Limit Exceeded,这就是边界条件出问题,区间出问题了.

但是Time Limit Exceeded 只是慢了点.

结果是正确的

1
int x = q[(l + r + 1) / 2]//当l = r - 1的时候,(l + r + 1) / 2 = r成为了右边界

Memory Limit Exceeded 结果错误

1
int x = q[r]

Memory Limit Exceeded 结果错误

用i的时候(将两个j都换成 i - 1就行了 )

1
2
quick_sort(q, l, i - 1);
quick_sort(q, i, r);//i - 1 + 1就是i
1
int x = q[(l + r) / 2]//当l = r - 1的时候,(l + r) / 2 = l成为了左边界

Memory Limit Exceeded 结果错误

1
int x = q[(l + r + 1) / 2]

结果正确

1
int x = q[r]

y总run的时候是对的,原因和上面我解释的一样

报错是Time Limit Exceeded ,说明只是慢了点.

结果是正确的

1
int x = q[l]

Memory Limit Exceeded 结果错误

==对于int x = q[随机]也是同理,你别让用j 的 时候 随机到 右边界上,别让用i 的 时候 随机到 左边界上.==

1105第三次

这次写的非常快,这就是前面把问题解决了,然后背的清楚的原因

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;

const int N = 100010;
int n;
int q[N];
void quick_sort(int q[], int l, int r);
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}
void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    while (i < j)
    {
        do
            i++;
        while (q[i] < x);
        do
            j--;
        while (q[j] > x);
        if (i < j)
            swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

最后一个记忆口诀:就是==第一次记忆的就是用到int x = q[(l + r ) / 2],然后是j.直接记忆就行了==.

==同理直接记忆用i - 1 替换j的话,就直接写成int x = q[(l + r + 1) / 2];==

我看y总到最后也是靠记忆的,,细节什么的都是靠前人了,,轮不到自己 去管了.

AcWing 786. 第k个数

给定一个长度为 nn 的整数数列，以及一个整数 kk，请用快速选择算法求出数列从小到大排序后的第 k个数。

用快排排序之后然后选择的话,时间复杂度是O(nlogn)了

快速选择算法的时间复杂度比较低,时间复杂度是O(n)的.

每次选择一个区间来递归.

image-20250103220518105

时间复杂度的计算

image-20250103220625656

归并排序

主要思想:分治

以整个数组的中间来分,,分成左边和右边.

快排是先分完在递归处理左边和右边

归并是先递归处理左右两边,再去做一些操作

归并步骤

  1. 确定分界点 mid = (l + r) / 2
  2. 递归排序左边和右边
  3. 归并——–合二为一(把两个有序的数组合并成一个有序的数组)

快排的分界点是数组里面随机一个数组里面的数值,归并的分界点是下标的中间值

快拍最难的是如何将当前区间划分成两端,归并最难的是如何把两个有序的序列合二为一.

把两个有序的序列合二为一的方法

双指针算法

两个指针分别指向两个序列开头的位置,用一个新的数组res来记录我们的答案.

image-20241103093843805

如果过程中两个序列的min相同,那么一般取第一个序列的min放到res[]里面.所以我们说归并排序是稳定的(快排是不稳定的,因此i 和 j遇到等于x的数都会swap(q[i], q[j]).

如果快排的数组里面的每一个元素都不同,快排就是稳定的

让快排的数组里面的每一个元素ai变成一个pair二元组<ai, i>,双关键字排序,这个时候快排就是稳定的了.)

==总结就是 双路归并,合二为一==

时间复杂度是O(nlogn)

对于归并排序而言 ,n除以logn次2就变成长度为1的区间,所以层数为logn,每一层的计算量又是O(n)的,总共的计算量就是O(nlogn)的

对于快拍而言,可以证明期望是logn层和每一层期望是O(n)的计算量.所以时间复杂度也是O(nlogn).

image-20241103094906623

787归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
using namespace std;
const int N = 1000010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    // k表示当前辅助数组tmp里面有多少个数了,已经合并多少个数了
    // i指向第一个序列的起点
    // j指向第二个序列的起点
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    }
    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++)
        q[i] = tmp[j];
}
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}

七次

1103第一次

犯的错误1

1
int mid = l + r >> 2;//写错了,应该是右移一位等于除以2

应该写成

1
int mid = l + r >> 1;//写错了,应该是右移一位等于除以2

犯的错误2

1
2
3
4
5
while (i <= mid && j <= r)
    if (q[i] < q[j])//q[i] <= q[j]
        tmp[k++] = q[i++];
    else
        tmp[k++] = q[j++];

为了保证归并的稳定性,应该写成

1
2
3
4
5
while (i <= mid && j <= r)
    if (q[i] <= q[j])//q[i] <= q[j]
        tmp[k++] = q[i++];
    else
        tmp[k++] = q[j++];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;
const int N = 1000010;//写错了,应该少些一个0
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = l + r >> 2;//写错了,应该是右移一位等于除以2
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];
    for (int i = l, j = 0; i <= r; i++, j++)//这个不能忘,是将临时数组里面的所有数都存回q里面去.
        q[i] = tmp[j];
}
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}

1104第二次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r);

int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);

    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
        printf("%d ", q[i]);
    return 0;
}
void merge_sort(int q[], int l, int r)
{
    if (l >= r)
        return; // 疑点一:l == r的时候应该也是返回,因为一个数组成的序列本身就是有序的
    int mid = (l + r) / 2;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int i = l, j = mid + 1;
    int k = 0;
    while (i <= mid && j <= r)
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++) // 疑点二:我竟然迟疑了一下,这里i和j应该等于谁
    // 每一层 递归 都要用到q[]的一部分,这部分是由l 和 r来确定在整个q[]数组里面的范围的,因此将tmp拷贝到q里面的时候,q很可能只是拷贝这一层递归对应的整个q数组的一小部分,所以只用复制到q的l到r的位置里面
    // 因此i作为q拷贝时候的下标,范围是l到r
    // 而j作为tmp拷贝时候都下标,范围是0到XXX,因为tmp每一层递归时候都重新从0开始放置从下一层递归传上来的两个有序数字序列合并后的结果
    // tmp里面有r - l + 1个数字,tmp下标的范围是0到r - l,当i = r的时候,j自然等于r - l
    {
        q[i] = tmp[j]; // 很明显tmp很多时候是占不满的,是很小的.因为当层的要你合并的两个有序数字序列很小
        //而且tmp也是在和q[]的很小一部分,例如l 和 r非常近的部分拷贝
    }
}

疑点1

1
2
if (l >= r)
    return; // 疑点一:l == r的时候应该也是返回,因为一个数组成的序列本身就是有序的

查看第一次写的代码,果然是l >= r,个人认为这里就是我注释给出的原因,因为一个数组成的序列本身就是有序的

疑点2

将tmp拷贝回q的时候都疑点,看我的注释.

1
2
3
4
5
6
7
8
9
for (i = l, j = 0; i <= r; i++, j++) // 疑点二:我竟然迟疑了一下,这里i和j应该等于谁
    // 每一层 递归 都要用到q[]的一部分,这部分是由l 和 r来确定在整个q[]数组里面的范围的,因此将tmp拷贝到q里面的时候,q很可能只是拷贝这一层递归对应的整个q数组的一小部分,所以只用复制到q的l到r的位置里面
    // 因此i作为q拷贝时候的下标,范围是l到r
    // 而j作为tmp拷贝时候都下标,范围是0到XXX,因为tmp每一层递归时候都重新从0开始放置从下一层递归传上来的两个有序数字序列合并后的结果
    // tmp里面有r - l + 1个数字,tmp下标的范围是0到r - l,当i = r的时候,j自然等于r - l
    {
        q[i] = tmp[j]; // 很明显tmp很多时候是占不满的,是很小的.因为当层的要你合并的两个有序数字序列很小
        //而且tmp也是在和q[]的很小一部分,例如l 和 r非常近的部分拷贝
    }

1105第三次

这次敲得也很快很熟练,背的很好.

不过我感觉应该按照y总说的,第一次就直接敲五遍,这样课上里面就没有任何疑问,不会像我一样隔了两天才做到熟练的程度

后续每天写一遍只是为了保证记忆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;

const int N = 100010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r);
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}
void merge_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) / 2, i = l, j = mid + 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int k = 0;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    }
    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];
    for (i = l, j = 0; i <= r; i++, j++)
        q[i] = tmp[j];
}

0104ac

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r);
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);
    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
        printf("%d ", q[i]);
    return 0;
}
void merge_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    }
    while (i <= mid)

        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];
    for (i = l, j = 0; i <= r; i++, j++)
        q[i] = tmp[j];
}

第一个疑点

1
int mid = l + r >> 1;

还是

1
int mid = (l + r)  / 2;

其实两个都是可以的, 但是y总写的时候是第一个,我个人认为第一个没有括号更好写,所以我也写第一个

第二个疑点

1
2
for (i = l, j = 0; i <= r; i++, j++)
    q[i] = tmp[j];

这个的记忆就是i表示q数组[l, r]这一部分,所以i从l开始,一直<=r.

j表示tmp数组,因为k从0开始的,所以j也从0开始,(事实上,每一层递归的tmp数组里面的前XXX数字都和q的[l, r]区间里面的数字个数一样,后面可能不一样,没戏想过),反正就记住,将tmp数组里面的数字都复制到q的[l, r]里面去.

==所以i是从l到r的 , j从0开始,到哪里我不关心,每复制一个就让i++, j++==

整数二分

有单调性就一定可以二分,,但是我可以二分的题目不一定非得要有单调性

所以说二分的本质并不是单调性.二分的本质是边界.

如果说我们可以找到这样的一个性质的话,让整个区间可以被一分为二,使得该性质在右边是满足的,在左边是不满足的.注意这两个没有交点,因为这是整数二分.(因为是整数,所以数轴上的点是跳跃的,至少相隔1个单位长度)

二分就可以寻找绿色的边界和 红色的边界.

二分找出绿色点和红色点就是两个不同 的模板了.

image-20241103104729862

二分出红色点,看红色边界点,也就是接下来是找红色边界点的过程

  1. 找中间值mid = l + r + 1 >> 1每次判断一下中间值是不是满足这样的性质 ,==check一下mid是不是满足红色这样一个性质==.
  2. if(check(mid))为true,则mid是在红色区间里面,则==红==色边界点是在[mid, r]里面来找(包括mid这个点,mid可能是红色边界点)…更新方式就是l = mid
  3. if(check(mid))为false,则mid是在绿色区间里面,则==红==色边界点是在[l, mid - 1]里面来找(不包括mid这个点,因为mid一定是不满足这个性质的,答案边界一定不再mid上面,至少要从mid左边一个位置开始看)…更新方式就是r = mid - 1

这种情况和int bsearch_2(int l, int r)是一样的

二分出绿色点,看绿色边界点,也就是接下来是绿色边界点的过程

  1. mid = l + r / 2;
  2. if(check(mid)) ==这时候的check就是check这个mid是否满足绿颜色的性质==
  3. true的话,mid在绿色区间,绿色边界点就在[l, mid],(包括mid,这个绿色边界点有可能在mid这个点上面).更新方式是r = mid
  4. false的话,mid在红色区间,,绿色边界点就在[mid +_1, r],,(不包括mid,)更新方式是l = mid + 1;

这种情况和int bsearch_1(int l, int r)是一样的

第一个问题,如何选择去用哪个模板

先写一个check函数,看更新区间,如果check是true说明要找的分界点在mid左边的话让r = mid此时前面的mid = l + r >> 1;如果check是true说明要找的分界点在mid右边的话让l = mid此时前面的mid = l + r + 1 >> 1;

(不补加一的话, mid + l + r / 2,此时令l = r - 1,则mid = l,那么更新操作是l = mid有等于l,泽会陷入死循环.)

具体写的时候不用考虑是红色点还是绿色点,,直接先写一个mid,,随便想一个check函数,更具check函数的值想一个我们的答案应该怎么样去划分,到底是l = mid还是 r = mid.

如果是l = mid的话,就在求mid的时候补上加一,第二种的话就不需要补上加一

二分模板如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 区间[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;
        else
            l = mid + 1;
    }
    return l;
}

// 区间[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;
}

根据实际题目来看如何理解

789数的范围

先找x的起始位置, 性质定成>=x, 这个时候相当于找绿色边界点.我先敲一下看看对不对.

刚刚自己敲了自己的想法,发现出现了程序卡在那里,,后来发觉是没有更改int mid = l + r + 1 >> 1;导致的出现死循环,所以卡死.

一:不能忘记更改mid的加一

二:程序卡了要立刻想到这是一个死循环,

提交了一遍自己的代码,发现报错segment fault.后来发现自己把

1
const int N = 100010;

写成

1
const int N = 10010;

导致的错误.

下面是自己写的,运行通过了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int q[N];

bool checkForMin(int mid, int x)
{
    if (q[mid] >= x)
        return true;
    else
        return false;
}

bool checkForMax(int mid, int x)
{
    if (q[mid] <= x)
        return true;
    else
        return false;
}
int minIndex(int l, int r, int x)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (checkForMin(mid, x))
            r = mid;
        else
            l = mid + 1;
    }
    if (q[l] != x)
        return -1;
    else
        return l;
}
int maxIndex(int l, int r, int x)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (checkForMax(mid, x))
            l = mid;
        else
            r = mid - 1;
    }
    if (q[l] != x)
        return -1;
    else
        return l;
}
int main(void)
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    while (m--)
    {
        int x;
        scanf("%d", &x);
        cout << minIndex(0, n - 1, x) << " " << maxIndex(0, n - 1, x) << endl;
    }
    return 0;
}

代码模板

二分模板介绍

二分模板如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 区间[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;
        else
            l = mid + 1;
    }
    return l;
}

// 区间[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;
}

根据实际题目来看如何理解

y总说几乎所有的二分都可以按照这个方法来解决,我就记住这两个板子了.

==个人记忆口诀:==

true的时候如果r = mid,false的是 l = mid + 1;那么int mid是否加一要看后面的如果是mid + 1那么就不用加一

true的时候如果l = mid,false的是 r = mid - 1;那么int mid是否加一要看后面的如果是mid - 1那么就用加一,也就是 int mid = l + r + 1 >> 1;(阴阳调和)

确定更新条件的时候只要记住mid落在红色还是绿色的区间里面,,我要找的是红色边界点还是绿色边界点.这个要找到红色边界点或者是绿色边界点位于l, r, mid三者里面取两者使得该边界点依旧在这两者里面(每次都保证新区间里面一定还是有答案的.)

同时这两者的距离最小.

(每次都要选择答案所在的区间进行处理, y总挂在嘴边的答案就是我们要找的红色分界点或者是绿色分界点,而这红色分界点或者绿色分界点在这道题目里面就是从左往右第一个>=x的数或者是从右往左第一个<=x的数字.判定红色区间或者绿色区间的条件就自然而然的出来,是按照大于等于x或者小于等于x划分的.

[!WARNING]

注意:找从左往右第一个>=x的数 和 找从右往左第一个<=x的数划分的红绿区间不一样.

这是两个自己定的性质,所以这是两次二分查找了,是完全不一样的划分条件和查找过程.

)

这两者就是要查找的新的区间,再将新区间和旧区间对比得知要如何更新l或者是r

当区间长度是1的时候,答案就一定在这里面了.这个区间里面的数就一定是答案了.

有解和无解的讨论

二分的模板一定要保证有解的,是题目的条件和题干意思执行某些情况是无解的.

为什么二分的模板一定是有解的,因为我们定义的这个性质一定是有解的.当我们定义一个性质之后,他一定是有边界的.我们的二分算法一定可以把这个边界给找出来.

就那上面那个题目举例子,一定可以找到从左往右第一个大于等于x的数,如果数组里面没有等于x 的数,那么我们二分找到的是第一个大于x的数.

二分算法还是找到了解,所以说二分算法是有解的.但我们没找到符合题目要求的等于x 的数,所以说对于这个题目来说是无解的.

二分之后通过这个性质判断出来原问题无解,但是二分的时候是一定可以找到边界的.所以二分的时候我们就不用考虑无解的情况了,无解的话一定是和题目有关的.我们可以根据二分的边界,来判断题目里面有没有解.

散步得到的自己深刻的理解

接下来是我通过这次散步加深的整数二分的理解:

一个区间,你通过一个你制定的条件,将区间分成红绿两个区间,

(你制定的条件是有方法的,不是随便制定的,是按照题干要你求的内容制定的.一句话,你制定的条件要让红绿区间的分界点就是题干要你求的内容,就是题干让你找的答案)

接着不断的取下标为mid的点,判断下标为mid的点落在红色区间还是绿色区间里面,然后通过l = mid或者是r = mid来缩小区间

(你每次缩小区间都能保证你要找的答案,你要找的红绿区间分界点都在缩小后的区间里面)

,一直缩小区间,直到区间里面只有一个数,这个数就是我们要找到答案,就是我们的红绿区间的分界点.

七次

1104第一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N]; // 记录自己每一次不太确定的部分,好像是N,不是n
bool checkStart(int mid, int k);
int bsearchStart(int q[], int l, int r, int k);
bool checkEnd(int mid, int k);
int bsearchEnd(int q[], int l, int r, int k);
int main(void)
{
    int m;                  // m表示询问次数
    scanf("%d %d", &n, &m); // 差点忘记给n和m加上引用符号
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);
    int k; // 要查询的元素
    while (m--)
    {
        scanf("%d", &k);
        int startIndex = bsearchStart(q, 0, n - 1, k);
        int startEnd = bsearchEnd(q, 0, n - 1, k);
        cout << startIndex << " " << startEnd << endl;
    }

    return 0;
}

bool checkEnd(int mid, int k)
{
    if (q[mid] <= k)
        return true; // 红色分界点就是从右往左第一个小于等于k的数字,就是题干要我们找的答案之二,就是数字k的结束位置
    else
        return false;
}
bool checkStart(int mid, int k)
{
    if (q[mid] >= k)
        return true; // 绿色分界点就是第一个大于等于k的数字,就是题干要我们找的答案之一,就是数字k的开始位置
    else
        return false;
}
int bsearchStart(int q[], int l, int r, int k)
{

    while (l < r)
    {                         // 应该是l < r不带等号,因为要保证循环结束的时候l == r从而区间里面只有一个数,这个数就是我们要找的答案,就是红绿区间分界点
        int mid = l + r >> 1; // mid应该在while里面,不然每一次循环mid都一直是最开始的l和最开始的r的和的一半
        if (checkStart(mid, k))
            r = mid; // 既然是r = mid就不用让mid = l + r + 1 >> 1
        else
            l = mid + 1;
    }
    if (q[l] != k) // 这是因为题干要求而在模板基础上做的改变.
        return -1; // 如果q[l] != k,说明这个数字q[]里面没有数值等于k 的数字,不存在该元素,就返回 -1
    else
        return l;
}
int bsearchEnd(int q[], int l, int r, int k)
{

    while (l < r)
    {                             // 应该是l < r不带等号,因为要保证循环结束的时候l == r从而区间里面只有一个数,这个数就是我们要找的答案,就是红绿区间分界点
        int mid = l + r + 1 >> 1; // mid应该在while里面,不然每一次循环mid都一直是最开始的l和最开始的r的和的一半
        if (checkEnd(mid, k))
            l = mid; // 既然是l = mid就必要让mid = l + r + 1 >> 1
        else
            r = mid - 1;
    }
    if (q[l] != k) // 这是因为题干要求而在模板基础上做的改变.
        return -1; // 如果q[l] != k,说明这个数字q[]里面没有数值等于k 的数字,不存在该元素,就返回 -1
    else
        return l;
}

写的时候的疑点:

第一个疑点

int q[N]; // 记录自己每一次不太确定的部分,好像是N,不是n

这里就是N,N表示数组的最大空间是MAX

n是你输入的元素个数,是size

第二个疑点

int bsearchStart(int q[], int l, int r, int k);和int bsearchEnd(int q[], int l, int r, int k);不用传数组int q[]因为你已经把他定义成全局变量了.只用传入数组的开始下标0,数组的结束下标n - 1,要查询的数字k

第三个疑点

是

1
while (l < r)

还是

1
while (l <= r)

代码应该是

1
while (l < r)

这样才能保证// 应该是l < r不带等号,因为要保证循环结束的时候l == r从而区间里面只有一个数,这个数就是我们要找的答案,就是红绿区间分界点

第四个疑点

我竟然在怀疑

1
int mid = l + r >> 1; // mid应该在while里面,不然每一次循环mid都一直是最开始的l和最开始的r的和的一半

是在while(l < r)的里面,还是在它的外面

经过一番自己的考量,发觉是在里面,因为// mid应该在while里面,不然每一次循环mid都一直是最开始的l和最开始的r的和的一半

1105第二次

这次敲得也很快, 但是应该课上第一次就把所有的问题解决的,不然时间真的不够.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N];
bool checkStart(int mid, int k);
bool checkEnd(int mid, int k);
int bsearchStart(int l, int r, int k);
int bsearchEnd(int l, int r, int k);
int main(void)
{
    int m;

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);

    while (m--)
    {
        int k;
        cin >> k;
        int indexStart = bsearchStart(0, n - 1, k);
        int indexEnd = bsearchEnd(0, n - 1, k);
        cout << indexStart << " " << indexEnd << endl;
    }
    return 0;
}
bool checkStart(int mid, int k)
{
    if (q[mid] >= k)
        return true;
    else
        return false;
}
bool checkEnd(int mid, int k)
{
    if (q[mid] <= k)
        return true;
    else
        return false;
}
int bsearchStart(int l, int r, int k)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (checkStart(mid, k))
            r = mid;
        else
            l = mid + 1;
    }
    if (q[l] != k)
        return -1;
    else
        return l;
}
int bsearchEnd(int l, int r, int k)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (checkEnd(mid, k))
            l = mid;
        else
            r = mid - 1;
    }
    if (q[l] != k)
        return -1;
    else
        return l;
}

0103第三次ac

几乎完全忘记的情况下回忆的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int m; // m表示询问个数
int q[N];
int findStartIndex(int l, int r, int k);
int findEndIndex(int l, int r, int k);
bool checkForStartIndex(int mid, int k);
bool checkForEndIndex(int mid, int k);

int main(void)
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);
    // 有m个询问
    while (m--)
    {
        int k;
        scanf("%d", &k);
        int startIndex = findStartIndex(0, n - 1, k);
        int endIndex = findEndIndex(0, n - 1, k);
        printf("%d %d\n", startIndex, endIndex);
    }
    return 0;
}

int findStartIndex(int l, int r, int k)
{
    // 粗略回忆一下,是通过不断地缩小要查找的区间从而最终找到目标的
    while (l < r) // 这里是<还是<=自己已经忘记 了
    {
        int mid = l + r >> 1;
        // 让左边的区间都是满足这个性质的,右边的区间都是不满足这个性质的
        // 这里找元素 k的起始位置,那么这个元素k的起始位置就是我们的目标,也就是我们的分界点
        // 元素k的右边,包括元素k都是>= k  的; 元素k的左边都是小于元素k的
        // 如果q[mid]满足小于元素k的性质,那我们要在mid的右边去找我们的 分界点

        // 一些记忆点, if里面都是更新l, else里面都是更新r
        // 让我回忆回忆
        if (checkForStartIndex(mid, k))
            l = mid + 1; // 因为mid指向的数一定小于k,所以不可能是mid指向的数  是   k的起始位置
        else
            r = mid;
    }
    if (q[l] == k)
        return l;
    else
        return -1;
}
int findEndIndex(int l, int r, int k)
{
    // 粗略回忆一下,是通过不断地缩小要查找的区间从而最终找到目标的
    while (l < r)
    {
        int mid = l + r + 1 >> 1; // 这里的记忆口诀是看常数的出现,上面函数出现的常数是+ 1, 所以不用在这里+1; 这个函数出现的常数是-1,所以就要在这里+ 1
        // 让左边的区间都是满足这个性质的,右边的区间都是不满足这个性质的
        // 这里找元素 k的终止位置,那么这个元素k的终止位置就是我们的目标,也就是我们的分界点
        // 元素k的右边都是> k  的; 元素k的左边包括元素k都是<=元素k的
        // 如果q[mid]满足<=元素k的性质,那我们要在mid的右边去找我们的 分界点

        // 一些记忆点, if里面都是更新l, else里面都是更新r
        // 让我回忆回忆
        if (checkForEndIndex(mid, k))
            l = mid; // q[mid]满足<=元素k,那么q[mid]是有可能就是元素k的终止位置的
        else
            r = mid - 1;
    }
    if (q[l] == k)
        return l;
    else
        return -1;
}
// 找到最左边的 k
bool checkForStartIndex(int mid, int k)
{
    if (q[mid] < k) // 难道都找的是左边区间满足的性质么????
                    // 个人认为找左边区间满足的性质,这样true的情况就直接更新l.符合先l后r的习惯
        return true;
    else
        return false;
}
bool checkForEndIndex(int mid, int k)
{
    if (q[mid] <= k) // 难道都找的是左边区间满足的性质么????
        return true;
    else
        return false;
}

第一个疑点

1
while (l < r) // 这里是<还是<=自己已经忘记 了

就是l<r,你就和快排一起学的,所以就和快排一起记忆,快排里面的就是递归终止条件是

1
if( l >= r) return;

快排后面的循环是while(i < j)

所以你也记住这里就是while(l < r)

第二个疑点

1
2
if (q[mid] < k) // 难道都找的是左边区间满足的性质么????
                // 个人认为找左边区间满足的性质,这样true的情况就直接更新l.符合先l后r的习惯
1
// 一些记忆点, if里面都是更新l, else里面都是更新r

并不是都是固定找左边区间满足的性质.也并不是if里面都是更新l, else里面都是更新r

但是我发现我这样固定找左边区间满足的性质,最后相应的做修改也没问题.但是为了稳定我还是按照y总的思路,,找的是带等于号的性质,如果满足就返回true.

这样的好处就是if(true) 更新l或者r的时候都不用在mid的基础上+1或者- 1;

第三个疑点

1
int mid = l + r + 1 >> 1; // 这里的记忆口诀是看常数的出现,上面函数出现的常数是+ 1, 所以不用在这里+1; 这个函数出现的常数是-1,所以就要在这里+ 1

这里记忆的没错,就是看这个函数对应 的 更新l和更新r的操作的里面出现的常数.

口诀:如果是+1就不用修正.如果是-1就修正让mid 后面 的表达式+1;

0103第四次ac

这次是标准的,成功ac了.记忆还是很重要的,很难完全理解.记忆一部分,理解一部分才能回忆写出来.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int m; // m表示询问个数
int q[N];
int bsearchStart(int l, int r, int k);
int bsearchEnd(int l, int r, int k);
bool checkStart(int mid, int k);
bool checkEnd(int mid, int k);

int main(void)
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);
    // 有m个询问
    while (m--)
    {
        int k;
        scanf("%d", &k);
        int startIndex = bsearchStart(0, n - 1, k);
        int endIndex = bsearchEnd(0, n - 1, k);
        printf("%d %d\n", startIndex, endIndex);
    }
    return 0;
}
int bsearchStart(int l, int r, int k)
{
    // 元素k的起始位置,把它作为分界点,看左右区间的性质,按照y总的将有等于号的设定为性质,且返回true
    // 也就是元素k的右边,包括元素k都是>= k的
    while (l < r)
    {
        int mid = l + r >> 1;
        if (checkStart(mid, k))
            r = mid;
        else
            l = mid + 1;
    }
    if (q[l] == k)
        return l;
    else
        return -1;
}
int bsearchEnd(int l, int r, int k)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        // 把元素k的终止位置作为分界点,元素k的左边包括元素k都是<= k的,把这个作为check条件
        if (checkEnd(mid, k))
            l = mid;
        else
            r = mid - 1;
    }
    if (q[l] == k)
        return l;
    else
        return -1;
}
bool checkStart(int mid, int k)
{
    if (q[mid] >= k)
        return true;
    else
        return false;
}
bool checkEnd(int mid, int k)
{
    if (q[mid] <= k)
        return true;
    else
        return false;
}

浮点数二分

浮点数二分也是一个边界问题,浮点数没有整除,所以没有边界问题,比较简单.

思想都是一样的,时刻要保证我们要找的答案(就是我们要找的分界点)在我们的最短区间内,每一次通过mid点来判断一下我们的答案在mid的左边还是mid的右边从而更新l或者r

当我们的区间长度很小的时候,我们就认为我们找到了答案

举一个开平方根的例子

这好像就是牛顿二分法不断逼近求平方根的过程

我写的时候犯了两个错误

一是while( r - l > 1e-6)写成了while( r - l <= 1e-6)

我记得这部分我在C++PrimerPlus里面学习的时候我就有感受,但是每次都懵懵懂懂导致老是犯错.

大家都是嘴上一说逻辑就知道while(test)里面的test应该写啥,我每次都慢一拍.

我应该这样子矫正自己,

循环结束的条件是XXX,那么循环的test就应该是XXX的补集.

或者是如果test满足就一直循环直到test不满足.

别看循环小,但是逻辑很重要.

二是把double mid写成 int mid,这部分很重要,每次写int的时候就要想到double.就和每次写new第一想法就应该是delete一眼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;

int main(void)
{
    double x;
    cin >> x;
    double l = 0, r = x;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid >= x)
            r = mid;
        else
            l = mid;
    }
    printf("%f", l);
    return 0;
}

image-20241103135634330

image-20241103140452106

y总一个经验值,如果保留n位小数,那么就写r - l > 1e-(n + 2)

七次

1104第一次

d

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;

int main(void)
{
    double x;
    cin >> x;
    double l = 0, r = x;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid >= x)
            r = mid;
        else
            l = mid;
    }
    printf("%f", l);
    return 0;
}

d

写的时候的错误:

第一个错误

习惯性把

1
2
3
double x;
double l = 0, r = x;
    double mid = (l + r) / 2;

都写成int类型导致的错误,我说过了,每次想到int就要想到为什么不能写double呢????

看到int就想到double

1105第二次

之后的次数都坐着道题目

  1. 数的三次方根

写对了,到时候习题课看怎么写的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
using namespace std;

int main(void)
{
    double n;
    cin >> n;

    if (n > 0)
    {
        double l = 0, r = 10010;
        while (r - l > 1e-8)
        {
            double mid = (l + r) / 2;
            if (mid * mid * mid >= n)
                r = mid;
            else
                l = mid;
        }
        printf("%.6f", l);
    }
    else
    {
        n = -n;
        double l = 0, r = 10010;
        while (r - l > 1e-8)
        {
            double mid = (l + r) / 2;
            if (mid * mid * mid >= n)
                r = mid;
            else
                l = mid;
        }
        printf("%.6f", -l);
    }

    return 0;
}

这道题目的正确答案是这个么????

我看看y总 习题课 视频

DONE

==最终的记忆还是要看文字描述的思路,然后自己慢慢回忆起来代码是怎么写的.要有从精简的文字概括到复现代码的过程才能记得牢靠.==

后记：

今天晚上陪妈妈散步的时候突发奇想想复习一下昨天学习的算法内容，本来是想自己随便回忆一下作为复习的，不过既然妈妈在旁边，那就讲的通俗易懂讲给妈妈听。这样自己既做到了复习，又充实了散步的时间。

当然我也想到了20年到21年看过的学习视频，这就是费曼学习法。教学相长也。

在我给妈妈讲这四个算法的时候，我仿佛找回了自己小学三年级第一次学围棋时候的快乐，当时自己觉得围棋很有趣，每次妈妈来接自己的时候自己都会跟她说今天围棋学了什么，一开始两周我妈在我的讲述下也学会了围棋，甚至还能下赢我（当然她是大人，战胜了三年级的小孩还是有可能的）.后来随着围棋越学越深,我讲不清楚围棋了,我妈也听不懂了.然后她就再也没陪我下棋过.可能是从那时候开始我觉得围棋没有那么让我开心了.

现在重拾了这段经历,更何况自己还要在家里呆一段时间,今天一整个白天都荒废摆烂了,晚上却有着般奇妙的经历,不管怎么样,我要坚持下去,每天都学新的算法,然后讲给妈妈听,让别人能听懂才能凸显自己对这件事情的理解.更何况我确实教学相长了,我发现我对整数二分的理解更深了,我对快速排序和归并排序的记忆和细节理解的更好了,我对递归有了更深的理解.也让我愿意今天重新敲一遍代码来复习昨天讲的内容.

接下来是我通过这次散步加深的整数二分的理解:

一个区间,你通过一个你制定的条件,将区间分成红绿两个区间,

(你制定的条件是有方法的,不是随便制定的,是按照题干要你求的内容制定的.一句话,你制定的条件要让红绿区间的分界点就是题干要你求的内容,就是题干让你找的答案)

接着不断的取下标为mid的点,判断下标为mid的点落在红色区间还是绿色区间里面,然后通过l = mid或者是r = mid来缩小区间

(你每次缩小区间都能保证你要找的答案,你要找的红绿区间分界点都在缩小后的区间里面)

,一直缩小区间,直到区间里面只有一个数,这个数就是我们要找到答案,就是我们的红绿区间的分界点.

PS1:这也引出了y总的理解,把这四个知识点放在一起,都是类似大问题分解成小问题来解决.

PS2:这也引出了我的理解,二分问题之所以数学意义上是按照二分算法步骤证明一定能找到解的,是因为区间为一的时候(区间退化到平凡情况,这个平凡情况就恰好是满足条件的)就是我们的要找到答案.

归并排序也是,不断分区间分到最后只有一个数字的时候,这一个数字就恰好是有序的(因为一个数字组成的序列天然是有序的)

快速排序也是,快排递归到最后一层的时候区间只有一个数字,而这个区间也是天然有序.(emmmm,也许是这样,我对这个的理解还不清楚)

PS3:

有些时候非专业知识,非老师讲的东西我并不一定相信是对的,尤其是自己 的理解,可能有很多偏差,可能只对了一半,可能完全是错的,但这并不妨碍我去理解它.因为理解本事就是为了记忆服务的,,也许我理解歪了,也许我理解的不是事实,但只要把知识点记住就是有效的.(就像化学一样,你初中学的知识和化合物规律高中就说初中不完全对,甚至直接推翻,你高中学的大学就说高中不完全对,甚至直接推翻,但这并不影响你初中学的时候,你高中学的时候去尝试理解这个知识点和规律,不影响你通过自己的尝试理解去记忆这个知识点和规律.)