知识点指南

Binary Search

Binary search finds a value by repeatedly halving a range. In AIO-style problems it often searches for the smallest possible answer that passes a feasibility test.

什么时候使用

读题时可以留意这些信号。

The data is sorted.
A yes/no check is monotonic: once true, it stays true; or once false, it stays false.
The task asks for minimum possible or maximum possible value.

常见错误

提交前可以检查这些小陷阱。

Writing a non-monotonic feasibility check.
Creating an infinite loop with wrong boundary updates.
Returning high/low incorrectly for min vs max searches.

怎么写成代码

把知识点翻译成变量、循环、判断和更新。

Choose low and high so the answer is inside the range.
Write a can(mid) function that returns true/false.
Move high down when mid works for a minimum search.
Move low up when mid does not work.

在 Block 题里长什么样

答题时通常会看到这些步骤被拆成代码块。

1Set search bounds.
2Repeat while low < high.
3Compute mid.
4Run feasibility check.
5Keep or discard half of range.
6Output final boundary.

题目里怎么出现

读题时先找这些信号，再决定答案区应该选哪些 blocks。

The story asks for smallest capacity/radius/time/cost.
Trying a value lets you decide whether that value is enough.
If one value works, every larger/smaller value also works.

Minimum working answer

一个小型模板，展示代码和 blocks 的对应关系。

C++

int low = 0, high = MAX;
while (low < high) {
    int mid = (low + high) / 2;
    if (can(mid)) high = mid;
    else low = mid + 1;
}
cout << low << '\n';

Python

low, high = 0, MAX
while low < high:
    mid = (low + high) // 2
    if can(mid):
        high = mid
    else:
        low = mid + 1
print(low)

对应 block 顺序

1Initialise low and high.
2Loop while range is not collapsed.
3Compute mid.
4Check whether mid works.
5Move high or low.
6Output low.