算法基础--二分

本文主要是介绍算法基础--二分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

二分

二分是一种常用且非常精妙的算法，常常是我们解答问题的突破口，二分的基本用途是在单调序列或单调函数中做查找操作，因此当问题的答案具有单调性时，就可以通过二分把求解转化为判定(根据复杂度理论，可知判定的难度小于求解)，这使得二分的应用范围变得很广泛
二分
二分法，在一个单调有序的集合或函数中查找一个解，每次分为左右两部分，判断解在哪个部分中并调整上下界，直到找到目标元素，每次二分后都将舍弃一半的查找空间，因此效率很高。

二分法的思想是不断将待求解区间平均分成两份，根据求解区间中点的情况来确定目标元素所在的区间，这样就把解的范围缩小了一半。

显然，二分算法的复度为O(二分次数×单次判定复杂度)。

二分函数写法

int BinarySearch(int a[],int size,int p)
{
	int L=0;
	int R=size-1;
	while(L<=R)
	{
		int mid=L+(R-L)/2;
		if(p==a[mid])
		  return mid;
		else if(p>a[mid])
		  L=mid+1;
		  else R=mid-1;
	}
	return -1;
}//复杂度O（log(n)) 

二分答案写法

1。整数定义域上的二分
【代码实现】

int Erfen(int L, int R)
{ int L=1，R=n, ans；
while(L <=R)
{
int mid=(L+R)>>1;
if(check(mid）ans=mid，L=mid+1；∥若满足要求，记下答案，并根据题意缩减范围
else R=mid-1;
}
return ans;
}

2。实数域上的二分
【代码实现】

int Erfen( double I, double r)
{∥dlt=0.001(根据题目要求决定精度)
double mid;
while(fabs(I-r)>dlt)
{
mid=(1+r)/2.0;
if( check(mid))r=mid;
else l=mid;
}
return l;
};

如上所述，如果我们指定二分的次数t，那么对于初始的求解区间长度L，算法结束后r-1的值会是L/2^t，根据这个值判断精度是否达到我们的要求即可。

二分法常见模型

1。二分答案
最小值最大(或是最大值最小)问题，这类双最值问题常常选用二分法求解，也就是确定答案后，配合贪心、DP等其他算法检验这个答案是否合理，将最优化问题转换为判定性问题。例如，将长度为n的序列a分成最多m个连续段，求所有分法中每段和的最大值的最小是多少?
2。二分查找
用具有单调性的布尔表达式求解分界点，比如在有序数列中求数字x的排名

二分答案
1、定义 二分答案与二分查找类似，即对有着单调性的答案进行二分，大多数情况下用于求解满足某种条件下的最大（小）值。
2、答案单调性

答案的单调性大多数情况下可以转化为一个函数，其单调性证明多种多样，如下：
1、 移动石头的个数越多，答案越大（NOIP2015跳石头）。
2、 前i天的条件一定比前 i + 1 天条件更容易（NOIP2012借教室）。
3、 满足更少分配要求比满足更多的要求更容易（NOIP2010关押罪犯）。
4、满足更大最大值比满足更小最大值的要求更容易（NOIP2015运输计划）。
5、 时间越长，越容易满足条件（NOIP2012疫情控制）。

最大值最小化问题
(l和r分别为初始时区间的下界和上界)
①当二分区间为[l,mid] [mid+1,r]时：

while(l<r)
{
    int mid=(l+r)>>1;
    if(check(mid))
    {
        r=mid;
    }
    else
    {
        l=mid+1;
    }
}当r==l时，a[r]即为答案

最小值最大化问题
当二分区间为[l,mid-1] [mid,r]时：

while(l<r)
{
    int mid=(l+r+1)>>1;
    if(check(mid))
    {
        l=mid;
    }
    else
    {
        r=mid-1;
    }
}当r==l时，a[r]即为答案

这篇关于算法基础--二分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！