源码下载：
https://pan.baidu.com/s/1wMsUK4hZpdttFzOK66n3mQ?pwd=x7a7提取码 x7a7
先进入《视频教程及配套源码》，再进入《C++算法》。
在线看视频：
https://www.bilibili.com/video/BV1nL411Q7DY/
1.1.基础1.1.1.最简单的情况a.情况简述
数组已经按升序排好序。
假定要找的数一定存在。
如果存在重复的数，返回任意一个。
b.原理
如果中间数和目标数相等，返回中间数索引。
如果中间数小于目标数，则目标数一定不在前半部分。
如果中间数大于目标数，则目标数一定不在后半部分。
假定数组区域是左闭右开区间，中间索引=（左索引+右索引)/2。
c.测试数据
从0到4中找1。
轮次 | 待查数据 | 中间数 |
第一轮 | 0 1 23 4 | 2 |
第二轮 | 0 1 | 1 |
从1到5中查找4。
轮次 | 待查数据 | 中间数 |
第一轮 | 1 234 5 | 3 |
第二轮 | 4 5 | 5 |
第三轮 | 4 | 4 |
1.1.2.重复数据返回第一个a.情况简述
数组已经按升序排好序。
假定要找的数一定存在。
如果存在重复的数，返回第一个。
b.原理
如果中间数小于目标数，则目标数一定不在前半部分。
如果中间数大于目标数，则目标数一定不在后半部分。
如果中间数等于目标数，则目标数一定不在后半部分。由于左半部分必须包括中间数，所以左开右闭区间。
c.测试数据
从1,2中寻找2。
轮次 | 待查数据 | 索引 | 中间数 |
第一轮 | 12 | (-1,1] | 1 |
第二轮 | 2 | (0,1] | 2 |
从2,2,3中寻找2。
轮次 | 待查数据 | 索引 | 中间数 |
第一轮 | 2 23 | (-1,2] | 2 |
第二轮 | 22 | (-1,1] | 2 |
第三轮 | 2 | (-1,0] | 2 |
从2,3,4中寻找2。
轮次 | 待查数据 | 索引 | 中间数 |
第一轮 | 2 34 | (-1,2] | 3 |
第二轮 | 23 | (-1,1] | 2 |
第三轮 | 2 | (-1,0] | 2 |
1.1.3.重复数据返回最后一个a.情况简述
数组已经按升序排好序。
假定要找的数一定存在。
如果存在重复的数，返回最后一个。
b.原理
一，如果中间数小于目标数，则目标数一定不在左边、中间，可能在右边。
二，如果中间数大于目标数，则目标数一定不在右边、中间，可能在左边。
三，如果中间数等于目标数，则目标数一定不在左边，可能在中间、右边。
数据 | 左 | 中 | 右 |
左闭右开 | |||
0,1,2,3 | 0,1 | 2((0+4)/2) | 3 |
0,1,2 | 0 | 1 | 2 |
0,1 | 0 | 1 | |
左开右闭 | |||
0,1,2,3 | 0 | 1（(-1+3)/2） | 2,3 |
0,1,2 | 0 | 1,2 | |
0,1 | 0 | 1 | |
结论：右（左）开，中间数就和右（左）区间合并，可以保持数据量均衡，左右数量相差不超过1。结合原理三，用左闭右开区间。 | |||
使用左闭右开（中右合并）后，情况分类 | |
中间数<目标数 | 中右 |
> | 左 |
= | 中右 |
结论：小于等于可以合并 | |
c.测试数据
寻找 | 期望值 | |
0123 | 0 | 0 |
0123 | 1 | 1 |
0123 | 2 | 2 |
1123 | 1 | 1 |
0113 | 1 | 2 |
1.1.4.循环代替递归
循环结束的条件：元素数量小于2。计算的元素数量可能是0，也可能是负数（非法数据）。由于是二分，所以左右边界一个不变， 一个变成中间位置。
1.1.5.目标数不一定存在a.如果目标数不存在，返回-1
解决方法：返回前，判断是否等于目标值，如果不是返回-1。
b.如果目标数不存在，返回它应该插入的位置
左开右闭 | |
数据（寻找0） | 左右中间索引 |
1,3,5,7 | 0,4,2 |
1,3 | 0,2,1 |
1 | 0,1,0结束 |
数据（寻找2） | 左右中间索引 |
1,3,5,7 | 0,4,2 |
1,3 | 0,2,1 |
1 | 0,1结束 |
数据（寻找4） | 左右中间索引 |
1,3,5,7 | 0,4,2 |
1,3 | 0,2,1 |
3 | 1,2,1结束 |
数据（寻找6） | 左右中间索引 |
1,3,5,7 | 0,4,2 |
5,7 | 2,4,3 |
5 | 2,3,2结束 |
数据（寻找8） | 左右中间索引 |
1,3,5,7 | 0,4,2 |
5,7 | 2,4,3 |
7 | 3,4,3结束 |
规律：
if (vec[left] < iTarget)
{
return left+1;
}
1.1.6.stl的二分函数a.小于、等于、大于iNum的数
const int iNum = 3;
auto it1 = data.lower_bound(iNum);
auto it2 = data.upper_bound(iNum);
[data.begin(),it1) 表示小于iNum的数。
[it1,it2)表示等于iNum的数。
[it2,data.end())表示大于iNum的数。
b.大于、等于iNum1小于等于iNum2的数
const int iNum1 = 3,iNum2=7;
auto it1 = data.lower_bound(iNum1);
auto it2 = data.upper_bound(iNum2);
视频顺便演示了大于iNum1小于iNum2。
c.对向量二分
const int iNum1 = 3,iNum2=7;
std::sort(data.begin(), data.end());
auto it1 = std::upper_bound(data.begin(), data.end(),iNum1);
auto it2 = std::lower_bound(data.begin(), data.end(), iNum2);
d.降序
见视频。
e.通过vector的v[1]查找
std::sort(data.begin(), data.end(), [](const std::vector& v1, const std::vector& v2)
{return v1[1] < v2[1]; });
auto it1 = std::lower_bound(data.begin(), data.end(), iNum1, [](const std::vector& v1, int iNum)
{
return v1[1] < iNum;
});
auto it2 = std::upper_bound(data.begin(), data.end(), iNum1, [](int iNum, const std::vector& v2)
{return iNum < v2[1]; });
1.2.习题1.2.1.最大亲密度
有若干包饼干，每包饼干的数量记录在数组nums中，比如：{4,1，7，5} ,分配给若干（如：3）小朋友。
每种分配方案的亲密度：任意两个小朋友饼干数的差的绝对值的最小值。
求所有分配方案中的最大亲密度。
分配方案{1,7,5}的亲密度=min(7-1,5-1,7-5}=2
分配方案{4,7,5}的亲密度=min(7-4,5-4,7-5}=1
分配方案{4,1,5}的亲密度=min(4-1,5-4,5-1}=1
分配方案{4,1,7}的亲密度=min(4-1,7-4,7-1)=3
1.解决思路
先按升序排序。
完成函数is，判断是否存在方案能够满足亲密只大于等于iQinMi。
因为要找最大值，所以中值符合的时候，抛弃左边。中值跟随右边，用左开右闭。
2021年目标：完成新书《闻缺陷则喜》,本博客右上公告有下载、阅读链接。