二分查找的讲义和视频

源码下载：

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。

从1到5中查找4。

1.1.2.重复数据返回第一个a.情况简述

数组已经按升序排好序。

假定要找的数一定存在。

如果存在重复的数，返回第一个。

b.原理

如果中间数小于目标数，则目标数一定不在前半部分。

如果中间数大于目标数，则目标数一定不在后半部分。

如果中间数等于目标数，则目标数一定不在后半部分。由于左半部分必须包括中间数，所以左开右闭区间。

c.测试数据

从1,2中寻找2。

从2,2,3中寻找2。

从2,3,4中寻找2。

1.1.3.重复数据返回最后一个a.情况简述

数组已经按升序排好序。

假定要找的数一定存在。

如果存在重复的数，返回最后一个。

b.原理

一，如果中间数小于目标数，则目标数一定不在左边、中间，可能在右边。

二，如果中间数大于目标数，则目标数一定不在右边、中间，可能在左边。

三，如果中间数等于目标数，则目标数一定不在左边，可能在中间、右边。

c.测试数据

1.1.4.循环代替递归

循环结束的条件：元素数量小于2。计算的元素数量可能是0，也可能是负数（非法数据）。由于是二分，所以左右边界一个不变， 一个变成中间位置。

1.1.5.目标数不一定存在a.如果目标数不存在，返回-1

解决方法：返回前，判断是否等于目标值，如果不是返回-1。

b.如果目标数不存在，返回它应该插入的位置

规律：

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年目标：完成新书《闻缺陷则喜》,本博客右上公告有下载、阅读链接。