基础算法模板之二分

二分

1. 算法分析

对于一个有序的序列，在查找某个值时可以优先考虑中间值与待查找值的关系来缩减查找范围，每次可以缩减一半，因此称为二分。
由于每次处理的数据量变为原来的一半，因此时间复杂度为o(\(log_2\)n)。

2.代码实现

二分可以分为整数二分和浮点数二分两种，整数二分有两种模板，分别对应不同的情况（目的是处理边界值情况）

• 整数二分

// 一般用于求最小值或符合条件的位于最左侧的值
int b_serch1(int l,int r)
{
	while(l < r)
	{
		int mid = l + r >> 1;
		if(check(mid)) r = mid; // mid落在目标值右侧且mid可能是目标值
		else l = mid + 1;
	}
	return l;
}

// 一般用于求最大值或求符合条件的位于最右边的值
int b_serch2(int l,int r)
{
	while(l < r)
	{
		int mid = l + r + 1 >> 1;
		if(check(mid)) l = mid; // mid落在目标值左侧且mid可能是目标值
		else r = mid - 1;
	}
	return l;
}

/* 
记忆与区分:
	r = mid 对应 mid = l + r >> 1;
	l = mid 对应 mid = l + r + 1 >> 1;
*/

• 浮点数二分

double b_serch3(double l,double r)
{
	while(r - l > 1e-6) // 根据题目要求选择精度
	{
		double mid = (l + r) / 2;
		if(check(mid)) r = mid; // mid落在目标值的右侧
		else l = mid;
	}
	return l;
}