Bisection (integer bisection and floating point bisection)

Problems that dichotomy can solve

 It is used to find a single point problem that satisfies the meaning of the problem , Some personality quality divides the interval into satisfactions and unsatisactions 
 Two halves of , The dichotomy can find the two boundaries of this property （ That is, the boundary that does not satisfy the property and the boundary that satisfies the property 
 The border ）, But it is very important to pay attention to the boundary problem 

The essence of dichotomy

 The essence of dichotomy is to replace search with a decision problem , Gradually narrow the range 
 Lock the answer , The essence of two parts is not monotonicity .

The condition of dichotomy

 Be sure to look in an ordered sequence of numbers .

The idea of dichotomy

Set a section [l,r], Some property will be interval [l,r] In two parts , The first part does not satisfy this property , The latter half satisfies this property , The dividing point of the first part is point （1） Interval is [l,(1)], The dividing point of the latter part is point （2） Interval is [(2),r].
1. Find the interval [l,r] In the middle mid
2. Check mid Whether this property is satisfied , Determine whether it is satisfied or not , according to mid Update the interval to narrow the range .

To get a dichotomous question, we must first think about which property can be divided into good intervals , determine mid How to narrow the interval after .

Split template （ Integer dichotomy ）

There are two bisection templates according to different intervals

1. When the interval [l,r] Divide into [l,mid] and [mid+1,r] when ,
 update operation 
             r=mid( The answer range is 【l,mid】)
    or      l=mid+1( Answer interval 【mid+1,r】)
 Calculation mid There is no need to add 1.（ General point finding （2））

int bsearch_1(int l,int r)
{
    while(l<r)
    {
      int mid=l+r>>1;		// Round down 		
      if(check(mid))	r=mid;
      else	l=mid+1;
    }
    return l;
}

2. When the interval [l,r] Divide into [l,mid-1] and [mid,r] when ,
 update operation 
       r=mid-1( The answer range is 【mid,r】)
 or   l=mid( The answer range is 【l,mid-1】)
 Calculation mid Need to add 1.( General point finding （1）)

int bsearch_2(int l,int r)
{
    while(l<r)
    {
    int mid=l+r+1>>1;		// Round up 
    if(check(mid))	l=mid;
    else	r=mid-1;
   }
   return 1;
}

Floating point binary

 Compared with integer bisection, floating-point bisection has no boundary , You can also use the template of integer bisection 
 Here are some examples to explain ：
eg: seek x The square root of 
#include<iostream>
using namespace std;
int main()
{
	double x;
	cin>>x;
	double l=0,r=x;
	while(r-l>1e-8)
	{
	   double mid=(l+r)/2;
	   if(mid*mid>=x)
	     r=mid;
	   else
	     l=mid;
	}
	printf("%lf\n",l);
	return 0;
}