入门级-二分

---
## 0、猜数游戏

一个人（以下简称玩家1 ）在心中默想一个数（以下简称x ），另一个人（以下简称玩家2 ）则通过询问来尝试x 。而玩家1 每次只能对玩家2 所猜测的数进行三个回答：

+ 回答大于x

+ 回答小于x

+ 回答等于x 
                        
---
## 程序实现
```c
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
  srand(time(0));
  int y = 0; 
  int x = rand() % 100 + 1;
  int cnt = 0;
  while(1)
  {
    cnt++;
    cout << "请输入你猜的数：" << endl;
    cin >> y;
    if(x == y){ cout << "You Win!" << endl;break;}
    if(x < y){ cout << "大了。" << endl;}
    if(x > y){ cout << "小了。" << endl;}
   }
   cout << "total:" << cnt << "times." << endl;
  
  return 0;
}

```

---

## 1、二分算法

当枚举的对象是**单调序列**时，就可以通过二分算法进行优化，快速逼近到正确解的位置。

由于单调的特征，我们可以每次计算 $mid = (L+R) / 2$，每次根据 $mid$ 的判定结果，排除掉左区间 $[L, mid]$        或右区间 $(mid, R]$。
---
```
A[] = {1, 2, 3, 4, 5, 5, 5, 9, 10};
k = 4;
```
例如－假设序列 $A$ 单调递增，查找值为 $k$：

如 $a[mid] > k$，则对于右区间所有下标 $i$，都有 $a[i] > k$，因此可以让 $R=mid-1$;

如 $a[mid] < k$，则对于左区间所有下标 $i$，都有 $a[i] < k$，因此可以让 $L=mid+1$。

---

## 2、常用场景

二分的前提是**单调性**，典型的场景比如：

- 查找答案
- 二分区间
- 函数求解
- 最优值
- 最小值最大化
- 最大值最小化

---

## 3、抽象模型

---

### 3.1 二分模型

状态空间分为左右两个子区间，[L, mid] 和 (mid, R]

$check(mid)$ 用来判定 $mid$（维度）对应的状态是否满足右侧条件，为真则将 $R$ 往 $mid - 1$ 变，为假则将 $L$ 往 $mid + 1$ 变;

循环以上过程，直到 $L$ 和 $R$ 重合之后的下一次变化，让 $R$ 变到 $L$ 左边，$mid$ 的开闭情况根据试题而定，影响最终结果的取值（为 $L$或 $R$）。

---

代码实现：
```c++
int ans = 0;
bool check(int mid)
{
  return a[mid] >= k;
}
while (L <= R) 
{
  int mid = (L + R) / 2;
  if (check(mid))
    R = mid - 1, ans = mid;
  else
    L = mid + 1;
}
cout<< ans << endl;

```

---

### 3.2 check函数和解

$check(mid)$ 函数表示 $mid$ 对应的状态落在左侧还是右侧区间，用来指导 $L$ 或 $R$ 的变化。

在二分循环结束后，$L$ 在右区间的最左端，$R$ 在左区间的最右端，因此要根据试题来设计 $check$ 函数（实际就是设计左右区间的开闭），最后取 $L$ 或 $R$ 为解。

---

例如：

- 第一个大于等于：$mid>= k$ 表示右侧，$mid<k$ 表示左侧，解取 $L$（右区间的最左端）
- 第一个大于：$mid>k$  表示右侧，$mid<=k$ 表示左侧，解取 $L$（右区间的最左端）
- 最后一个小于等于：$mid>k$ 表示右侧，$mid<=k$表示左侧，解取 $R$（左区间的最右端）
- 最后一个小于：$mid>=k$ 表示右侧，$mid<k$ 表示左侧，解取 $R$（左区间的最右端）

---
## 例题与练习

|二分查找例题|
|---|
|[P591  查找给定的K](http://39.99.183.126:8888/p/591)|
|[**CCFPB06D10**  找数](http://39.99.183.126:8888/p/CCFPB06D10)|
|[P699  查找位置](http://39.99.183.126:8888/p/699)|
|[寻找峰值](http://39.99.183.126:8888/p/4450)|

---

### 分析：

#### 1、朴素思路

朴素算法自然是枚举了，由于题目是找第一个等于，所以从左到右枚举，找到第一个就break，然后输出，如果循环结束还找不到（正常结束的下标==n+1），就输出－1。

显然，复杂度为O(n)。

#### 2、二分思路

由于序列为单调的（本题为单调不减），可以考虑用二分的方法快速逼近。

---

### 3.3 解题思路

一般根据试题提炼出题目，识别维度、状态、解，假如可以转化成对状态进行判定来求解的，就可以用枚举实现。

进一步，如果状态区间是单调的，就可以使用二分来逼近求解。

---

## 4、实数二分

### 4.1 二分模板

```c++
double eps = 1E-6;
double L = 0, R = 1000000;
while(L <= R)
 {
  double mid = (L + R) / 2;
  if(check(mid))
    R = mid - eps;//eps是一个很小的数
  else
    L = mid + eps;
}
```

---

### 4.3 指定循环次数

有时候如果不好控制精度，也可以直接控制循环次数。例如设定循环次数为t次，则最后循环结束后R-L的值会是L/2^t。

```c++
int t = 100;
while(t-- > 0) {
//....
}
```

---

## 5. 二分答案

解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了「二分答案」。二分答案的前提是答案所在的值域满足单调性。

---

|二分答案例题|
| --------------------------------------------------------------- |
|[P28  切割绳子](http://39.99.183.126:8888/p/28)|

---

| 二分答案练习题|
| --------------------------------------------------------------- |
| [CCFPB06D11月度开销](http://39.99.183.126:8888/p/CCFPB06D11) |
|[CCFPB06E04奶牛音节](http://39.99.183.126:8888/p/CCFPB06E04) |
|[P596  [NOIP2015 提高组] 跳石头](http://39.99.183.126:8888/p/596)|
|[P320 不太甜的糖果](http://39.99.183.126:8888/p/320)|

---