整数二分查找

提要

使用二分的条件:具有单调性

注意:二分的思想看似简单,但其实很容易出错

整数二分模板

以单调递增序列的二分为例

给出两个模板:

在单调递增序列中找到xx的后继(大于x的第一个数),也就是大于等于x的第一个数的位置
在单调递增序列中找到xx的前驱(小于x的第一个数),也就是小于等于x的第一个数的位置

// 找到x或x的后继
int bin_search(int *a, int n, int x)	// a 的编码为 [0, n), 左开右闭区间,下面同理
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int mid = left + (right - left) / 2;	// 取左中位值
		if (a[mid] >= x) right = mid;
		else left = mid + 1;		// 防止死循环
	}					// 循环结束时 l = r
	return left;
}

// 找到x或x的前驱
int bin_search(int *a, int n, int x)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int mid = left + (right - left + 1) / 2;	// 取右中位数
		if (a[mid] <= x) left = mid;
		else right = mid - 1;
	}
	return left;
}

对left, right 的处理

值得注意,第一个模板中循环的结尾left = mid + 1,其原因是整数二分存在取整的问题
例如当 left 等于 2, right 等于 3 时 mid 等于 2,若取 left = mid ,一次循环结束 left 和 right 的值都没有变,程序陷入死循环,解决方法是像模板一样 left = mid + 1

对mid的处理

整数二分的关键是对中间值mid的处理

以第一个模板为例,mid取值有以下几种方法

实现方法 使用条件 可能出现的问题
mid = (left + right) / 2 left >= 0, right >= 0,
left + right 未溢出
(1)负数情况下会出现向0取整问题
(2)left + right 可能溢出
mid = left + right >> 1 left + right 未溢出 left + right 可能溢出
mid = left + (right – left) >> 1 left – right 未溢出 left 和 right 一正一负时 right – left 可能溢出

值得注意的是,上表中第一个实现方式中向0取整问题是指当 left + right 大于 0 使取的是左中位数,而当 left + right 小于 0 时取的是右中位数,正负区间没有统一取左中位数或右中位数,而后两种方法就没有这个问题,当然在对数组进行二分时,三种实现方法都是可行的

如果是对数组进行二分,因为其下标都大于等于0,个人觉得用上表中的第三个更好

单调递减序列二分

了解上面这些之后,我们也能写出单调递减序列的二分模板

//   找到最后一个大于等于x的数的位置
int bin_search(int *a, int n, int x)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int mid = left + (right - left + 1) / 2;
		if (a[mid] >= x) left = mid;
		else right = mid - 1;
	}
	return left;
}

// 找到第一个小于小于x的数的位置
int bin_search(int *a, int n, int x)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int mid = left + (right - left) / 2;
		if (a[mid] <= x) right = mid;
		else left = mid + 1;
	}
	return left;
}

一个方便(?)记忆的方法

我们观察两个模板的话,会发现:

如果是 left = mid 的话, mid 就要取右中位值
如果是 right = mid 的话,mid 就要取左中位值

写二分的时候,可以先把 mid 写成左中位值,再写对应 left 和 right 的操作,最后再看前面的 mid 是否要改成右中位值

lower_bound() 和 upper_bound()

STL 提供了lower_bound(),upper_bound()这两个函数

lower_bound() 返回大于等于所查找数的最小位置
upper_bound() 返回大于所查找数的最小位置

利用 lower_bound()lower_bound() 我们可以实现如下的操作:

  • 查找第一个大于等于 x 的元素:pos = lower_bound(a, a + n, x) - a
  • 查找第一个大于 x 的元素:pos = upper_bound(a, a + n, x) - a
  • 查找第一个等于 x 的元素:pos = lower_bound(a, a + n, x) - a 并且 a[pos] == x
  • 查找最后一个小于等于 x 的元素:pos = upper_bound(a, a + n, x) - a - 1
  • 查找最后一个等于 x 的元素:pos = upper_bound(a, a + n, x) - a - 1 并且 a[pos] == x
  • 查找第一个小于 x 的元素:pos = lower_bound(a, a + n, x) - a - 1
  • 计算单调序列中 x 的个数:pos = upper_bound() - lower_bound()

注意:对长度为 n 的一段序列查找 x ,如果 x 大于序列中的最后一个数将返回 n
(将上述二分模板中r = n – 1 改为 r = n 的时,会跟上面两个函数一样返回 n)

原文地址:http://www.cnblogs.com/Panmaru/p/16917295.html

发表评论

您的电子邮箱地址不会被公开。