二分与三分

一：二分

　　在一个单调有限的区间上找一个值，每一次分左右两部分，判断是在左右哪两个区间，并及时调整上下界，直至找到了目标元素，就如他的名字一样，二分，不断把数据分成两半

　　但是对于解决实数类的问题，通常需要一个精确值，避免死循环

二：二分写法

　　1.整数定义域上的二分：

 1 bool Check(int p)
 2 {
 3     return p;
 4 }
 5 int Bt(int l,int r)
 6 {
 7     int ans=0,mid;
 8     while(l<=r)
 9     {
10         mid=(l+r)>>1,
11         Check(mid)?ans=mid,l=mid+1:r=mid-1;
12     }
13     return ans;
14 }

View Code

　　2.实数定义域上的二分：

 1 double DLT=0.1;
 2 bool Check(double p)
 3 {
 4     return p;
 5  } 
 6 int Bt(double l,double r)
 7 {
 8     double ans=0,mid;
 9     while(r-l>=DLT)
10     {
11         mid=(r+l)/2.0;
12         Check(mid)?ans=mid,l=mid:l=mid;
13     }
14 }

View Code

三：二分的常见模型

　　1.二分答案

　　　　最小值最大（最大值最小）

　　2.二分查找

　　　　单调数列中求排名，位置

　　3.代替三分

四：典型例题

　　1.愤怒的牛

　　　　(1).例题

　　　　(2).思路

　　　　(3).伪代码

　　2.Best Cow Fences

　　　　(1).例题

　　　　(2).思路

　　　　(3).伪代码

二分与三分

二分与三分

一：二分

二：二分写法

1.整数定义域上的二分：

2.实数定义域上的二分：

三：二分的常见模型

1.二分答案

2.二分查找

3.代替三分

四：典型例题

1.愤怒的牛

2.Best Cow Fences

五：三分

六；上级练习

未完待续~~~