admin管理员组文章数量:1647985
前言
C++算法与数据结构
打开打包代码的方法兼述单元测试
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
严格的来说：树状数组、线段树、快速指数幂、树上倍增等也是二分查找，这些内容如果多，会有单独的专题。
原理简述
不失一般性，我们以在升序数组nums中寻找小于等于x最大数为例。绿色表示可能是答案，红色表示一定不是答案，圈起来的数字表示是nums[mid]。mid = (left+right)/2，拆分成[0,mid)和[mid,right)。如果nums[mid] <= x 成立，抛弃左边；否则，抛弃右边。当只有一个元素时，循环结束。由于可能无解，所以还要判断唯一的元素是否是解。下面通过图表来说明。
。
原理证明
二分空间
不考虑双闭空间和双开空间，只考虑左闭右开空间[left,right)和左开右闭空间(left, right]。其空间大小为len= right -left。不失一般性，只证明左闭右开空间。将其拆分成左右两部分， [left,mid)和[mid,right)，其长度分别为len1,len2 ,mid=(left+right)/2。如果len为偶数：左部长度为：(right-left)/2，右半部分也是。如果len为奇数：mid = (left+right-1)/2，左部长度为：(right-left-1)/2，右部长度：(right-left+1)/2。即分别为：(len-1)/2和(len+1)/2，因为len为奇数，则前后两部分分别为：len/2和len/2+1。结论：如果len为偶数：左右两部长度相等，都为len/2。为奇数是：左右两部长度分别为：len/2,len/2+1。故当len>=2，两部分都变小，即具有收敛性。当len>=2,左右两部的长度，一定大于0。len为1时，结果已出，无需继续。即循环结束条件为：len<=1。
使用前提
存在Check(x)函数，x的取值范围是左闭右闭空间[left,right]，以下两种情况之一：
一，存在x1，left<=x1<=right+1。如果x<x1,Check(x)一定为true,否则一定为false。二分查找x1-1。下文称为二分尾端。
二，存在x1，left<=x1<=right+1。如果x<x1,Check(x)一定为false,否则一定为true。二分查找x1。下文称为二分首端。
二分尾端
双闭空间转成左闭右开空间的方式是：right++。参数范围为左闭右开空间[left,right)。如果Check(mid)为真，则x < mid，一定不是解，抛弃左部。即left = mid；
否则x>=mid一定不是解，抛弃右部，即right=mid。
二分首端
双闭空间转成左开右闭空间的方式：left–。参数范围为(left,right]。如果Check(mid)为真，x>mid一定不是解，抛弃，即right=mid；否则，x <= mid一定不是解，抛弃，即left=mid。
二分问题步骤
分三步：
判断是寻找末端还是寻找首端。
完成Check函数。
调用模板或封装类。
寻找值对应的下标
如果有多个相同的值，返回最后一个。类型：寻找末端。Check函数：a[mid] <= x。
如果有多个相同的值，返回第一个。类型：寻找首端。Check函数：a[mid] >=x。
标准库的两个函数lower和upper，都是寻找首端，Check函数分别：
a[mid] >=x 和a[mid] > x。
寻找大于x的最小偶数
错误解法
类型：寻找首端。Check函数: return (mid > x ) && ( 0 == x%2);
令x为2，则Check(1…5)的结果为：{false,false,false,true,false},不符合使用前提。
正确解法
Check函数改成：2*mid > x。Check(1…5)的结果为：{false,true,true,true,true}。
二分查找的结果为:2，将二分查找的结果乘以2，就是最终答案。
无解
被抛弃的一定不是解，留下来的可能解，也可能不是解。循环结束后，Check(唯一的元素)，如果为假，说明无解。
##. x的参数可以是double型
循环结束条件为len <= 0.00001。
小技巧
mid = left + (right-left)/2也是可行的。如果left为正数，可以避免溢出。
封装类、模板
二分查找
template<class INDEX_TYPE>
class CBinarySearch
{
public:
CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}
template<class _Pr>
INDEX_TYPE FindFrist( _Pr pr)
{
auto left = m_iMin - 1;
auto rightInclue = m_iMax;
while (rightInclue - left > 1)
{
const auto mid = left + (rightInclue - left) / 2;
if (pr(mid))
{
rightInclue = mid;
}
else
{
left = mid;
}
}
return rightInclue;
}
template<class _Pr>
INDEX_TYPE FindEnd( _Pr pr)
{
int leftInclude = m_iMin;
int right = m_iMax + 1;
while (right - leftInclude > 1)
{
const auto mid = leftInclude + (right - leftInclude) / 2;
if (pr(mid))
{
leftInclude = mid;
}
else
{
right = mid;
}
}
return leftInclude;
}
protected:
const INDEX_TYPE m_iMin, m_iMax;
};
二分查找最近接近的值
template<class Ptr, class T>
T Near(Ptr begin, Ptr end, const T& val, const T valDefault) {
auto it = lower_bound(begin, end, val);
if ((end == it) && (begin == it)) { return valDefault; }
if (end == it) { return *(--it); }
if (begin == it) { return *it; }
auto pre = prev(it);
return abs(*it - val) < abs(*pre - val) ? *it : *pre;
}
时间复杂度
O(logn)
入门级学习级难度(博文将陆续公开，估计2024年10月1号全部公开）
寻找首端
| 难度分 | |
|---|---|
| 1300. 转变数组后最接近目标值的数组和 | 1606 |
| 2187. 完成旅途的最少时间 | 1640 |
| 1870. 准时到达的列车最小时速 | 1675 |
| 3143. 正方形中的最多点数 | 1696 |
| 1011. 在 D 天内送达包裹的能力 | 1725 |
| 1954. 收集足够苹果的最小花园周长 | 1758 |
| 875. 爱吃香蕉的珂珂 | 1765 |
| 2064. 分配给商店的最多商品的最小值 | 1885 |
| 2594. 修车的最少时间 | 1915 |
| 1552. 两球之间的磁力 | 1919 |
| 2439. 最小化数组中的最大值 | 965 |
| 1760. 袋子里最少数目的球 | 1939 |
| 1482. 制作 m 束花所需的最少天数 | 1945 |
| 1201. 丑数 III | 2039 |
寻找尾端
| 难度分 | |
|---|---|
| 2424. 最长上传前缀 | 1604 |
| 2024. 考试的最大困扰度 | 1643 |
| 2226. 每个小孩最多能分到多少糖果 | 1646 |
| 1292. 元素和小于等于阈值的正方形的最大边长 | 1734 |
| 2576. 求出最多标记下标 | 1843 |
| 1838. 最高频元素的频数 | 1876 |
| 1898. 可移除字符的最大数目 | 1912 |
| 1802. 有界数组中指定下标处的最大值 | 1929 |
| 2861. 最大合金数 | 1981 |
| 2831. 找出最长等值子数组 | 1975 |
| 17. 礼盒的最大甜蜜度 | 2020 |
| 1648. 销售价值减少的颜色球 | 2050 |
系统的二分函数
| 难度分 | |
|---|---|
| 792. 匹配子序列的单词数 | 1695 |
| 825. 适龄的朋友 | 1697 |
| 2080. 区间内查询数字的频率 | 1702 |
| 826. 安排工作以达到最大收益 | 1708 |
| 2563. 统计公平数对的数目 | 1720 |
| 2070. 每一个查询的最大美丽值 | 1724 |
| 2856. 删除数对后的最小数组长度 | 1749 |
| 1146. 快照数组 | 1770 |
| 2601. 质数减法运算 | 1779 |
| 1658. 将 x 减到 0 的最小操作数 | 1817 |
| 2055. 蜡烛之间的盘子 | 1819 |
| 1477. 找两个和为目标值且不重叠的子数组 | 1850 |
| 2817. 限制条件下元素之间的最小绝对差 | 1889 |
| 2602. 使数组元素全部相等的最少操作次数 | 1903 |
| 1818. 绝对差值和 | 1934 |
| 2411. 按位或最大的最小子数组长度 | 1938 |
| 1488. 避免洪水泛滥 | 1973 |
| 911. 在线选举 | 2000 |
| 2271. 毯子覆盖的最多白色砖块数 | 2021 |
| LeetCode240:搜索二维矩阵 | 无 |
困难级算法
自己写二分算法
【二分查找】自写二分函数的总结
| 左闭右开 左开右闭 | C++算法：二分查找旋转数组 |
| 左闭右开 | C++二分查找算法的应用：长度递增组的最大数目 |
| 左闭右开 | C++二分查找算法的应用：最小好进制 |
| 左开右闭 | C++二分查找算法：阶乘函数后 K 个零 |
| 左开右闭 | C++二分查找算法的应用：第 N 个神奇数字 |
| 一题三解(暴力、二分查找算法、单指针):鸡蛋掉落 | |
| 左闭右开 左开右闭 | C++ 二分查找算法：山脉数组中查找目标值 |
| 左开右闭 | C++二分查找算法：查找和最小的 K 对数字 |
| 左闭右开 | C++二分算法的应用：寻找峰值原理、源码及测试用例 |
| 左开右闭 | C++二分查找算法：有序矩阵中的第 k 个最小数组和 |
| 左闭右开 | 【二分查找】你能穿过矩阵的最后一天 |
| 左闭右开 带视频 | 救生艇 |
| 左闭右开 | 同时运行 N 台电脑的最长时间 |
| 左闭右开 | 统计得分小于 K 的子数组数目 |
| 左闭右开 | 预算内的最多机器人数目 |
| 左闭右开 | 最大化城市的最小电量 |
有序映射
如果不做特别说明，key都是升序
| 值升序，淘汰键大的 | C++二分查找算法的应用：最长递增子序列 |
| 值升序，淘汰键大的 | C++二分查找算法的应用：俄罗斯套娃信封问题 |
| C++二分查找算法的应用：将数据流变为多个不相交区间 | |
| 值降序，淘汰键大的 | C++二分查找算法：132 模式枚举3 |
| 值升序，淘汰键大的 | C++二分查找算法：规划兼职工作 |
| 值升序，淘汰键小的 | C++二分查找算法：132 模式解法二枚举2 |
| 值升序，淘汰键小的 | C++二分查找算法：找到 Alice 和 Bob 可以相遇的建筑 |
| 值降序，淘汰键大的 | C++二分算法：得到山形数组的最少删除次数 |
| 值降序，淘汰键大的 | C++二分算法：最多可以参加的会议数目 II |
| 值无序 | C++二分查找算法：包含每个查询的最小区间 |
| 值降序，淘汰键小的 | 最大和查询 |
| 值降序，淘汰小的 | map 二分查找 离线查询 LeetCode:2736最大和查询 |
| 值降序，淘汰大的；值升序，淘汰小 | [键值皆有序map 线段树 数学 】100240. 最小化曼哈顿距离 |
对有序向量二分查找
| C++二分查找算法：最大为 N 的数字组合 | |
| C++二分查找算法：数组中占绝大多数的元素 | |
| C++二分向量算法：最多可以参加的会议数目 II | |
| C++二分查找：统计点对的数目 | |
| C++二分查找视频教程：两数之和 | |
| [二分查找]找出到每个位置为止最长的有效障碍赛跑路线 | |
| 使数组连续的最少操作数 | |
| 将数组分成两个数组并最小化数组和的差 | |
| 两个有序数组的第 K 小乘积 | |
| 花园的最大总美丽值 | |
| 花期内花的数目 | |
| 优质数对的数目 | |
| 带视频 | 长度最小的子数组 |
| 下一个更大元素 IV | |
| 最少得分子序列 | |
| 完成所有任务的最少时间 |
有序集合
C++二分查找算法：132 模式解法三枚举1
C++二分算法：找到最接近目标值的函数值
C++二分查找算法：132模式枚举3简洁版
C++二分查找或并集查找：交换得到字典序最小的数组
C++二分查找、离线算法：最近的房间
矩阵
【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II
【动态规划】【矩阵快速幂】【KMP】LeetCode2851. 字符串转换
树上倍增
【树上倍增】【树】 【换根法】3067. 在带权树网络中统计可连接服务器对数目
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
本文标签： 算法
版权声明：本文标题：C++二分查找算法 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1729489458a1202429.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论