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

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

更新中

陈远龙老师主讲 & 答疑

课程题单 - T1005

未购买 · 可先试学24节课

课程目录展开/折叠

视频时长：01:00:31

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

播放快捷键

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

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

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

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

本节课讲解到的源代码

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

1. 找到第1个大于等于x的位置-1

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

int a[100]; // 非递减 
int n;

// [L, R) 
// 第1个大于等于x的位置 STL lower_bound [L, R)
int bSearch(int a[], int n, int x)
{
    int l = 0, r = n;

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

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

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的位置-1

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

int a[100]; // 非递减 
int n;

// [L, R]
// 第1个大于x的位置 STL upper_bound [L, R)
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;
    while (l <= r)
    {
        int m = l + (r - l) / 2;
        if (a[m] > x) // 左区间里找 
        {
            ans = m;
            r = m - 1;
        }
        else // 右区间里找
            l = m + 1;
    }
    return ans; // return r + 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;
}

3. 找到第1个大于x的位置-2

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

int a[100]; // 非递减 
int n;

// [L, R)
// 第1个大于x的位置 STL upper_bound [L, R)
int bSearch(int a[], int n, int x)
{
    int l = 0, r = n;
}

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未能获得满意解答的，可以联系陈远龙老师答疑