有序数组的二分查找（Binary Search on a Sorted Array）

C++

参考资料（Resources）	内容	说明
C++	`lower_bound`、`upper_bound`	含示例

如需更多参考资料，请查看二分查找模块（Binary Search module），但该模块包含超出本模块范围的额外内容。

示例 - 干草捆计数（Example - Counting Haybales）

题目等级：白银级（Silver）- 简单（Easy）

由于每个点的取值范围在$0 \ldots 1\,000\,000\,000$之间，若用布尔数组存储干草捆的位置并计算其前缀和，会消耗过多的时间与内存。

相反，我们可以将所有干草捆的位置存入一个列表并对其排序。此时，我们可通过二分查找，在$\mathcal{O}(\log N)$时间内分别统计出位置至多为$B$的干草捆数量，以及位置小于$A$的干草捆数量，最后将这两个数量相减，即可得到最终答案。

不使用内置函数（Without Built-in Functions）

C++

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

void setIO(string name = "") {  // name is nonempty for USACO file I/O
	ios_base::sync_with_stdio(0);
	cin.tie(0);  // see Fast Input & Output
	// alternatively, cin.tie(0)->sync_with_stdio(0);
	if (!name.empty()) {
		freopen((name + ".in").c_str(), "r", stdin);  // see Input & Output
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

int main() {
	setIO("haybales");
	int bale_num;
	int query_num;
	cin >> bale_num >> query_num;
	vector<int> bales(bale_num);
	for (int &i : bales) { cin >> i; }

	sort(begin(bales), end(bales));
	// Returns the number of elements that are at most x
	auto atMost = [&](int x) {
		int lo = 0;
		int hi = bales.size();
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if (bales[mid] <= x) {
				lo = mid + 1;
			} else {
				hi = mid;
			}
		}
		return lo;
	};

	for (int i = 0; i < query_num; ++i) {
		int q_start;
		int q_end;
		cin >> q_start >> q_end;
		cout << atMost(q_end) - atMost(q_start - 1) << "\n";
	}
}

使用内置函数（With Built-in Functions）

C++

我们可以使用C++内置的lower_bound和upper_bound函数。

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

void setIO(string name = "") {  // name is nonempty for USACO file I/O
	ios_base::sync_with_stdio(0);
	cin.tie(0);  // see Fast Input & Output
	// alternatively, cin.tie(0)->sync_with_stdio(0);
	if (!name.empty()) {
		freopen((name + ".in").c_str(), "r", stdin);  // see Input & Output
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

int main() {
	setIO("haybales");
	int bale_num;
	int query_num;
	cin >> bale_num >> query_num;
	vector<int> bales(bale_num);
	for (int i = 0; i < bale_num; i++) { cin >> bales[i]; }

	sort(begin(bales), end(bales));
	for (int i = 0; i < query_num; i++) {
		int q_start;
		int q_end;
		cin >> q_start >> q_end;
		cout << upper_bound(begin(bales), end(bales), q_end) -
		            lower_bound(begin(bales), end(bales), q_start)
		     << "\n";
	}
}

练习题（Problems）

状态（Status）	来源（Source）	题目名称（Problem Name）	难度（Difficulty）	标签（Tags）
-	CF（Codeforces）	蜂窝网络（Cellular Network）	简单（Easy）	显示标签（Show Tags）：双指针（2P）、二分查找（Binary Search）
-	白银级（Silver）	奶牛利比（Cow-libi）	简单（Easy）	显示标签（Show Tags）：二分查找（Binary Search）