二分法与倍增法

二分法；倍增法。

概念

二分法在有序或单调的性质上，每次排除一半候选范围：找边界、判可行、求最大最小值都常用。写法上要分清「找第一个满足」与「找最后一个满足」，以及 mid 取 (l+r)/2 还是 (l+r+1)/2 避免死循环。倍增法用「2 的幂次步长」快速跳转：预处理倍增表、快速幂、或在大 n 上递推「上一轮结果」都是 CSP-J 常见形态。与 cspj.algo.sorting 区分：二分要求有序性来自题意或预处理，不是学排序本身；与 cspj.algo.recurrence-and-recursion 区分：倍增的递推常带「乘 2 跳步」结构，而不是相邻项线性组合。

CSP-J 常考

cspj-r1-2019 第 5 题：单选题，二分或单调性相关判断。
cspj-r1-2023 第 33–37 题：完善程序整段，实现二分查找或边界判定。
cspj-r1-2024 第 9 题：单选题，考查二分适用条件或复杂度。
cspj-r1-2021 第 41–42 题：完善程序，与倍增或快速跳转相关的填空。
cspj-r2-2023 第 1 题：复赛编程，约瑟夫型「隔 2 取 1」，n 达 10^9 需倍增递推。

// 二分：找最小 x 使得 ok(x) 为真（x 在 [lo, hi]）
while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (ok(mid)) hi = mid;
    else lo = mid + 1;
}
// 快速幂：倍增思想
long long pw(long long a, int e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a;
        a = a * a; e >>= 1;
    }
    return r;
}

易错点

二分 while 条件与更新写混：lo=mid 与 lo=mid+1 必须和「找左边界/右边界」配对，否则死循环或漏解。
完善程序里 mid=(l+r)/2 在极大 l、r 时溢出，应写 l+(r-l)/2（初赛若考到会出现在选项或代码行里）。
题意不单调仍硬二分：要先确认或转化为单调判定函数。

设有 $100$ 个已排好序的数据元素，采用折半查找时，最大比较次数为（）

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

（ 2 ）（矩形计数） 平面上有 $n$ 个关键点，求有多少个四条边都和 $x$ 轴或者 $y$ 轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。

试补全枚举算法。

程序

#include <iostream>using namespace std;struct point { int x, y, id;};bool equals(point a, point b) { return a.x == b.x && a.y == b.y;}bool cmp(point a, point b) { return ①;}void sort(point A[], int n) { for (int i = 0; i < n; i++) for (int j = 1; j < n; j++) if (cmp(A[j], A[j - 1])) { point t = A[j]; A[j] = A[j - 1]; A[j - 1] = t; }}int unique(point A[], int n) { int t = 0; for (int i = 0; i < n; i++) if (②) A[t++] = A[i]; return t;}bool binary_search(point A[], int n, int x, int y) { point p; p.x = x; p.y = y; p.id = n; int a = 0, b = n - 1; while (a < b) { int mid = ③; if (④) a = mid + 1; else b = mid; } return equals(A[a], p);}const int MAXN = 1000;point A[MAXN];int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> A[i].x >> A[i].y; A[i].id = i; } sort(A, n); n = unique(A, n); int ans = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (⑤ && binary_search(A, n, A[i].x, A[j].y) && binary_search(A, n, A[j].x, A[i].y)) { ans++; } cout << ans << endl; return 0;}

41（③）单选空位 ③3 分
③处应填 ( )

A
b - (b - a) / 2 + 1

B
(a + b + 1) >> 1

C
(a + b) >> 1

D
a + (b - a + 1) / 2

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

试补全枚举算法。

程序

42（④）单选空位 ④3 分
④处应填 ( )

A
!cmp(A[mid], p)

B
cmp(A[mid], p)

C
cmp(p, A[mid])

D
!cmp(p, A[mid])

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

1 #include <iostream>2 3 using namespace std;4 5 int n,k;6 7 int solve1()8 {9 int l = 0, r = n;10 while(l <= r){11 int mid = (l + r) / 2;12 if (mid * mid <= n) l = mid + 1;13 else r = mid - 1;14 }15 return l - 1;16 }17 18 double solve2(double x)19 {20 if (x == 0) return x;21 for (int i = 0; i < k; i++)22 x = (x + n / x) / 2;23 return x;24 }25 26 int main()27 {28 cin >> n >> k;29 double ans = solve2(solve1());30 cout << ans << ' ' << (ans * ans == n) << endl;31 return 0;32 }

28判断1.5 分
该算法最准确的时间复杂度分析结果为 $O(\log n+k)$ 。

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

29判断1.5 分
当输入为 9801 1 时，输出的第一个数为 99。

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

(寻找被移除的元素)问题: 原有长度为 $n+1$ 公差为 $1$ 等差数列，将数列输到程序的数组时移除了一个元素，导致长度为 $n$ 的连续数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right){
        int mid = left + (right - left) / 2;
        if (nums[mid] == mid + ①) {
            ②;
        } else {
            ③;
        }
    }
    return ④;
}
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    int missing_number = find_missing(nums);
    if (missing_number == ⑤) {
        cout << "Sequence is consecutive" << endl;
    }else{
        cout << "Missing number is " << missing_number << endl;
    }
    return 0;
}

程序

#include <iostream>#include <vector>using namespace std;int find_missing(vector<int>& nums) { int left = 0, right = nums.size() - 1; while (left < right){ int mid = left + (right - left) / 2; if (nums[mid] == mid + ①) { ②; } else { ③; } } return ④;}int main() { int n; cin >> n; vector<int> nums(n); for (int i = 0; i < n; i++) cin >> nums[i]; int missing_number = find_missing(nums); if (missing_number == ⑤) { cout << "Sequence is consecutive" << endl; }else{ cout << "Missing number is " << missing_number << endl; } return 0;}

33（①）单选空位 ①3 分
①处应填（）

A
1

B
nums[0]

C
right

D
left

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

(寻找被移除的元素)问题: 原有长度为 $n+1$ 公差为 $1$ 等差数列，将数列输到程序的数组时移除了一个元素，导致长度为 $n$ 的连续数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right){
        int mid = left + (right - left) / 2;
        if (nums[mid] == mid + ①) {
            ②;
        } else {
            ③;
        }
    }
    return ④;
}
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    int missing_number = find_missing(nums);
    if (missing_number == ⑤) {
        cout << "Sequence is consecutive" << endl;
    }else{
        cout << "Missing number is " << missing_number << endl;
    }
    return 0;
}

程序

34（②）单选空位 ②3 分
②处应填（）

A
left=mid+1

B
right=mid-1

C
right=mid

D
left=mid

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

(寻找被移除的元素)问题: 原有长度为 $n+1$ 公差为 $1$ 等差数列，将数列输到程序的数组时移除了一个元素，导致长度为 $n$ 的连续数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right){
        int mid = left + (right - left) / 2;
        if (nums[mid] == mid + ①) {
            ②;
        } else {
            ③;
        }
    }
    return ④;
}
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    int missing_number = find_missing(nums);
    if (missing_number == ⑤) {
        cout << "Sequence is consecutive" << endl;
    }else{
        cout << "Missing number is " << missing_number << endl;
    }
    return 0;
}

程序

35（③）单选空位 ③3 分
③处应填（）

A
left=mid+1

B
right=mid-1

C
right=mid

D
left=mid

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

(寻找被移除的元素)问题: 原有长度为 $n+1$ 公差为 $1$ 等差数列，将数列输到程序的数组时移除了一个元素，导致长度为 $n$ 的连续数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right){
        int mid = left + (right - left) / 2;
        if (nums[mid] == mid + ①) {
            ②;
        } else {
            ③;
        }
    }
    return ④;
}
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    int missing_number = find_missing(nums);
    if (missing_number == ⑤) {
        cout << "Sequence is consecutive" << endl;
    }else{
        cout << "Missing number is " << missing_number << endl;
    }
    return 0;
}

程序

36（④）单选空位 ④3 分
④处应填（）

A
left+nums[0]

B
right+nums[0]

C
mid+nums[0]

D
right+1

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

(寻找被移除的元素)问题: 原有长度为 $n+1$ 公差为 $1$ 等差数列，将数列输到程序的数组时移除了一个元素，导致长度为 $n$ 的连续数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right){
        int mid = left + (right - left) / 2;
        if (nums[mid] == mid + ①) {
            ②;
        } else {
            ③;
        }
    }
    return ④;
}
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    int missing_number = find_missing(nums);
    if (missing_number == ⑤) {
        cout << "Sequence is consecutive" << endl;
    }else{
        cout << "Missing number is " << missing_number << endl;
    }
    return 0;
}

程序

37（⑤）单选空位 ⑤3 分
⑤处应填（）

A
nums[0]+n

B
nums[0]+n-1

C
nums[0]+n+1

D
nums[n-1]

编程题

小苹果

C++时间 1 s内存 512 MB 文件 IO：apple.in → apple.out

小 Y 的桌子上放着 $n$ 个苹果从左到右排成一列，编号为从 $1$ 到 $n$ 。

小苞是小 Y 的好朋友，每天她都会从中拿走一些苹果。

每天在拿的时候，小苞都是从左侧第 $1$ 个苹果开始、每隔 $2$ 个苹果拿走 $1$ 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。

小苞想知道，多少天能拿完所有的苹果，而编号为 $n$ 的苹果是在第几天被拿走的？

输入格式

从文件 apple.in 中读入数据。

输入的第一行包含一个正整数 $n$ ，表示苹果的总数。

输出格式

输出到文件 apple.out 中。

输出一行包含两个正整数，两个整数之间由一个空格隔开，分别表示小苞拿走所有苹果所需的天数以及拿走编号为 $n$ 的苹果是在第几天。

样例

输入 1

输出 1

5 5

小苞的桌上一共放了 $8$ 个苹果。
小苞第一天拿走了编号为 $1$ 、 $4$ 、 $7$ 的苹果。
小苞第二天拿走了编号为 $2$ 、 $6$ 的苹果。
小苞第三天拿走了编号为 $3$ 的苹果。
小苞第四天拿走了编号为 $5$ 的苹果。
小苞第五天拿走了编号为 $8$ 的苹果。

数据范围

对于所有测试数据有： $1 \le n \le 10^9$ 。

测试点	$n \le$	特殊性质
$1 \sim 2$	$10$	无
$3 \sim 5$	$10^3$	无
$6 \sim 7$	$10^6$	有
$8 \sim 9$	$10^6$	无
$10$	$10^9$	无

特殊性质：小苞第一天就取走编号为 $n$ 的苹果。

部分分

20 分
测试点 $1 \sim 2$ ： $n \le 10$ ，无特殊性质。
30 分
测试点 $3 \sim 5$ ： $n \le 10^3$ ，无特殊性质。
20 分
测试点 $6 \sim 7$ ： $n \le 10^6$ ，特殊性质：小苞第一天就取走编号为 $n$ 的苹果。
20 分
测试点 $8 \sim 9$ ： $n \le 10^6$ ，无特殊性质。
10 分
测试点 $10$ ： $n \le 10^9$ ，无特殊性质。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

假设有序表中有 $1000$ 个元素，则用二分法查找元素 $X$ 最多需要比较（）次。