二分查找

对于一段序列，如果想找到某个元素，$O(n)$ 是最简单的方法。但如果序列有序，就可以利用单调性达成 $O(\log n)$ 的复杂度，这就是二分查找。

不妨看一道例题：

【深基13.例1】查找 - 洛谷

递归实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 2;
int a[N];
int binsearch(int l, int r, int x) {
	if (l >= r) {
        if (a[l] == x) return l;
        return -1;
	}
	int mid = l + (r - l) / 2;
	if (a[mid] >= x) return binsearch(l, mid, x);
	return binsearch(mid + 1, r, x);
}
int main()
{
	int n, m; scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
	}
	while (m--) {
		int x; scanf("%d", &x);
		cout << binsearch(1, n, x) << ' ';
	}
	return 0;
}

非递归实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 2;
int a[N];
int binsearch(int l, int r, int x) {
	while (l < r) {
		int mid = l + (r - l) / 2;
		if (a[mid] >= x) r = mid;
		else l = mid + 1;
	}
	if (a[l] == x) return l;
	else return -1;
}
int main()
{
	int n, m; scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
	}
	while (m--) {
		int x; scanf("%d", &x);
		cout << binsearch(1, n, x) << ' ';
	}
	return 0;
}

如果抛开“输出第一次出现的编号”这一要求，只需要找到某个存在的位置或判断不存在，那么可以改为：

int binsearch(int l, int r, int x) {
	if (l > r) return;
	int mid = l + (r - l) / 2;
	if (a[mid] == x) return mid;
	else if (a[mid] > x) return binsearch(l, mid - 1, x);
	return binsearch(mid + 1, r, x); 
}

如果要找最后一次出现的编号，可以改为：

int binsearch(int l, int r, int x) {
    if (l > r) return -1;
    int mid = l + (r - l) / 2;
    if (a[mid] == x) {
        int res = binsearch(mid + 1, r, x);
        // 往后找，要是没找到的话，mid 就是最后一次出现的编号
        return res == -1 ? mid : res;
    } 
    else if (a[mid] < x) return binsearch(mid + 1, r, x);
    return binsearch(l, mid - 1, x);
}

STL 中也有关于二分查找的函数：lower_bound() 和 upper_bound()，详见 C++ Standard Template Library STL 合集

二分答案

解题时，可以通过枚举答案然后判断是否合理来解题。若答案具有单调性，则可以使用二分答案的方法，以 $O(\log n)$ 的成本来枚举答案。