源码下载:
https://pan.baidu.com/s/1wMsUK4hZpdttFzOK66n3mQ?pwd=x7a7 提取码 x7a7
先进入《 视频教程及配套源码》,再进入《C++算法》。
在线看视频:
https://www.bilibili.com/video/BV1nL411Q7DY/
文章来源:https://www.toymoban.com/news/detail-510246.html
1.1. 基础
1.1.1. 最简单的情况
a. 情况简述
数组已经按升序排好序。
假定要找的数一定存在。
如果存在重复的数,返回任意一个。
b. 原理
如果中间数和目标数相等,返回中间数索引。
如果中间数小于目标数,则目标数一定不在前半部分。
如果中间数大于目标数,则目标数一定不在后半部分。
假定数组区域是左闭右开区间,中间索引=(左索引+右索引)/2。
c. 测试数据
从0到4中找1。
轮次 |
待查数据 |
中间数 |
第一轮 |
0 1 2 3 4 |
2 |
第二轮 |
0 1 |
1 |
从1到5中查找4。
轮次 |
待查数据 |
中间数 |
第一轮 |
1 2 3 4 5 |
3 |
第二轮 |
4 5 |
5 |
第三轮 |
4 |
4 |
1.1.2. 重复数据返回第一个
a. 情况简述
数组已经按升序排好序。
假定要找的数一定存在。
如果存在重复的数,返回第一个。
b. 原理
如果中间数小于目标数,则目标数一定不在前半部分。
如果中间数大于目标数,则目标数一定不在后半部分。
如果中间数等于目标数,则目标数一定不在后半部分。由于左半部分必须包括中间数,所以左开右闭区间。
c. 测试数据
从1,2中寻找2。
轮次 |
待查数据 |
索引 |
中间数 |
第一轮 |
1 2 |
(-1,1] |
1 |
第二轮 |
2 |
(0,1] |
2 |
从2,2,3中寻找2。
轮次 |
待查数据 |
索引 |
中间数 |
第一轮 |
2 2 3 |
(-1,2] |
2 |
第二轮 |
2 2 |
(-1,1] |
2 |
第三轮 |
2 |
(-1,0] |
2 |
从2,3,4中寻找2。
轮次 |
待查数据 |
索引 |
中间数 |
第一轮 |
2 3 4 |
(-1,2] |
3 |
第二轮 |
2 3 |
(-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<int>的v[1]查找
std::sort(data.begin(), data.end(), [](const std::vector<int>& v1, const std::vector<int>& v2)
{return v1[1] < v2[1]; });
auto it1 = std::lower_bound(data.begin(), data.end(), iNum1, [](const std::vector<int>& v1, int iNum)
{
return v1[1] < iNum;
});
auto it2 = std::upper_bound(data.begin(), data.end(), iNum1, [](int iNum, const std::vector<int>& 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。
因为要找最大值,所以中值符合的时候,抛弃左边。中值跟随右边,用左开右闭。文章来源地址https://www.toymoban.com/news/detail-510246.html
到了这里,关于二分查找的讲义和视频的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!