第17课 CSP-J大纲知识专题&初赛真题精讲

全面备考2025 CSP-J 初赛 & 复赛直播课

更新中

陈远龙老师主讲 & 答疑

课程题单 - T1005

未购买 · 可先试学24节课

课程目录展开/折叠

视频时长：01:11:32

视频 PPT&板书讲课代码课后练习

播放快捷键

播放/暂停：空格（或鼠标单击）全屏：F（或鼠标双击）退出全屏：Esc

快进10 / 30 / 60秒：方向键→ / Ctrl + 方向键→ / Shift + 方向键→

快退10 / 30 / 60秒：方向键← / Ctrl + 方向键← / Shift + 方向键←

本节课讲解配套PPT&板书：

本节课讲解到的源代码

源代码下载：第17课 CSP-J大纲知识专题&初赛真题精讲-源代码下载

1. 查找最后一个小于等于x的位置-1

#include <bits/stdc++.h>
using namespace std;

int n;
int a[100];

// [L, R]
// 最后一个小于等于x的位置 
// 1. 小于等于x
// 2. 最后一个（最大的位置） 
// 符合条件的最大值 角度去思考 
int bSearch(int a[], int n, int x)
{
    int l = 0, r = n - 1;
    while (l <= r)
    {
        int m = l + (r - l) / 2;
        /* 
        if (a[m] > x)
            r = m - 1; // 在左区间查找 
        else
            l = m + 1; // 在右区间查找 
        */
        if (a[m] <= x)
            l = m + 1; // 在右区间查找更大的解 
        else
            r = m - 1; // 在左区间查找可行解 
    }
    return r; // return l - 1;
}

int bSearch2(int a[], int n, int x)
{
    int l = 0, r = n - 1;
    int ans = -1;
    while (l <= r)
    {
        int m = l + (r - l) / 2;
        if (a[m] <= x) // check(m) check(mid) 
        {
            ans = m;
            l = m + 1; // 在右区间查找更大的解 
        }
        else
            r = m - 1; // 在左区间查找可行解 
    }
    return ans; // return l - 1;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> a[i];

    int x;
    cin >> x;    
    cout << bSearch(a, n, x) << endl;
    cout << bSearch2(a, n, x) << endl;

    return 0;
}

2. 查找第1个大于等于x的位置

#include <bits/stdc++.h>
using namespace std;

int n;
int a[100];

// [L, R]
// 第一个大于等于x的位置 
// 1. 大于等于x
// 2. 第一个（最小的位置） 
// 符合条件的最小值 角度去思考 

// 课间练习 
//  第一个大于x的位置 
// 1. 大于x
// 2. 第一个（最小的位置） 
// 符合条件的最小值 角度去思考 

int bSearch(int a[], int n, int x)
{
    int l = 0, r = n - 1;
    while (l <= r)
    {
        int m = l + (r - l) / 2;
        if (a[m] >= x)
            r = m - 1;
        else
            l = m + 1;
    }
    return l; // return r + 1
}

int bSearch2(int a[], int n, int x)
{
    int l = 0, r = n - 1;
    int ans = n; // ans的初始值就是代表找不到的情况 
    while (l <= r)
    {
        int m = l + (r - l) / 2;
        if (a[m] >= x)
        {
            ans = m;
            r = m - 1; // 往左找更小的解 
        }
        else
            l = m + 1; 
    }
    return ans;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> a[i];

    int x;
    cin >> x;    
    cout << bSearch(a, n, x) << endl;
    cout << bSearch2(a, n, x) << endl;

    return 0;
}

本节课无课后练习

本节课答疑

建议大家有问题先通过AI答疑（比如：DeepSeek 等），AI时代需要学会使用AI辅助学习

陈远龙老师视频讲解：如何使用DeepSeek进行答疑？

通过AI未能获得满意解答的，可以联系陈远龙老师答疑