二分查找题解

Level3-4-Q1 查找（洛谷P2249 深基13.例1 查找）

• 分析：查找目标数字的左边界
• 示例代码 while循环

#include <iostream>
using namespace std;

const int MAXN = 1e6 + 6;
int n, m, k;
int a[MAXN];

int bs(int a[], int start, int end, int k)
{
	while(start < end) {
		int mid = (start + end) >> 1;
		if(a[mid] >= k) {
			end = mid;
		} else {
			start = mid + 1;
		}
	}

	if(a[start] == k)
		return start;
	else
		return -1;
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= m; i++) {
		cin >> k;
		cout << bs(a, 1, n, k) << " ";
	}

	return 0;
}

• 示例代码 – 递归

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 1e6 + 6;
int n, m, k;
int a[MAXN];

int bs(int a[], int start, int end, int k)
{
	if(start >= end) {
		if(a[start] == k)
			return start;
		else
			return -1;
	}

	int mid = (start + end) >> 1;
	if(a[mid] >= k)
		return bs(a, start, mid, k);
	else
		return bs(a, mid + 1, end, k);
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= m; i++) {
		cin >> k;
		cout << bs(a, 1, n, k) << " ";
	}

	return 0;
}

STL提供的二分查找函数

STL提供了常用的二分查找相关的函数

• std::lower_bound() 返回有序表里第一个大于等于给定值的指针或迭代器；
• std::upper_bound() 返回有序表里第一个大于给定值的指针或迭代器；
• std::binary_search() 返回给定值是否在有序表里存在。

头文件

#include <algorithm>

binary_search

• binary_search 返回给定值是否在有序表里存在。
• 函数模板：

binary_search(start,  end,  key)

参数说明：start：数组首地址 end：数组最后一个元素的下个地址 key: 需要查找的值

lower_bound

• lower_bound() 返回有序表里第一个大于等于给定值的指针或迭代器；
• 函数模板:

lower_bound(begin, end, key, cmp)

从数组的 begin 位置到 end-1 位置二分查找第一个大于或等于 key 的数字，找到返回该数字的地址，不存在则返回 end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound

• upper_bound() 返回有序表里第一个大于给定值的指针或迭代器
• 函数模板:

upper_bound(begin, end, key, cmp)：

从数组的 begin 位置到 end-1 位置二分查找第一个大于key 的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址 begin,得到找到数字在数组中的下标。

定制比较函数

• 比较函数

bool cmp (int a, int b)
{
	return a > b;
}

• 重载 <

struct Node {
	int len;
	int last;

	bool operator < ( const node &b ) const {
		if (last == b.last)
			return len > b.len;
		return last < b.last;
	}
};

• 仿函数

struct Mycmp
{
    bool operator()(int a, int b) const
    {
        return a > b;
    }
};

参考代码

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

bool cmp (int a, int b)
{
	return a > b;
}

struct Mycmp
{
    bool operator()(int a, int b) const
    {
        return a > b;
    }
};

int main()
{
	int a[7] = {11, 22, 33, 44, 44, 55, 66};
	int idx;
	idx = lower_bound(a, a+7, 44) - a;
	printf("1->%d- idx: %d\n", 44, idx);

	sort(a, a+8, cmp);
	sort(a, a+8, Mycmp());

	idx = lower_bound(a, a+7, 44, greater<int>()) - a;
	printf("2<- %d- idx: %d\n", 44, idx);

	idx = lower_bound(a, a+7, 44, cmp) - a;
	printf("3<- %d- idx: %d\n", 44, idx);

	idx = lower_bound(a, a+7, 44, Mycmp()) - a;
	printf("4<- %d- idx: %d\n", 44, idx);

}

Level3-4-Q2 A-B 数对（洛谷P1102 A-B 数对）

分析

A – B = C的数对. C是给定值. 那么对于B来说, 求出 A = B + C, 有几个A, 就有多少对.

直接暴力枚举, 时间复杂度  , 会超时.

二分查找可以降低复杂度, 所以需要首先对数组进行排序. 然后找到A的左边界和大于A的左边界, 它们的差即为数组中数值为A的元素个数.

参考代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 2e5 + 10;

long long a[MAXN], n, c, ans;

int main()
{
    cin >> n >> c;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++)
    {
        ans += ((upper_bound(a + 1, a + n + 1, a[i] + c) - a) -
                (lower_bound(a + 1, a + n + 1, a[i] + c) - a));
    }

    cout << ans;
    return 0;
}