Skip to content

Latest commit

 

History

History
222 lines (213 loc) · 61.6 KB

binary-search.md

File metadata and controls

222 lines (213 loc) · 61.6 KB

二分查找

全部标签

数据结构

数组 矩阵 链表 双向链表 单调栈 队列 单调队列 堆(优先队列) 哈希表 字符串 字符串匹配 二叉树 二叉搜索树 最小生成树 有序集合 拓扑排序 最短路 强连通分量 欧拉回路 双连通分量 并查集 字典树 线段树 树状数组 后缀数组

算法

枚举 递归 分治 回溯 贪心 动态规划 排序 桶排序 计数排序 基数排序 归并排序 快速选择 二分查找 记忆化搜索 深度优先搜索 广度优先搜索 双指针 位运算 前缀和 计数 滑动窗口 状态压缩 哈希函数 滚动哈希 扫描线

其他

数学 数论 几何 博弈 模拟 组合数学 随机化 概率与统计 水塘抽样 拒绝采样 数据库 设计 数据流 脑筋急转弯 交互 迭代器 多线程


题号 标题 题解 标签 难度 力扣
4 寻找两个正序数组的中位数 [✓] 数组 二分查找 分治 🔴 🀄️ 🔗
33 搜索旋转排序数组 [✓] 数组 二分查找 🟠 🀄️ 🔗
34 在排序数组中查找元素的第一个和最后一个位置 [✓] 数组 二分查找 🟠 🀄️ 🔗
35 搜索插入位置 [✓] 数组 二分查找 🟢 🀄️ 🔗
69 x 的平方根 [✓] 数学 二分查找 🟢 🀄️ 🔗
74 搜索二维矩阵 [✓] 数组 二分查找 矩阵 🟠 🀄️ 🔗
81 搜索旋转排序数组 II [✓] 数组 二分查找 🟠 🀄️ 🔗
153 寻找旋转排序数组中的最小值 [✓] 数组 二分查找 🟠 🀄️ 🔗
154 寻找旋转排序数组中的最小值 II [✓] 数组 二分查找 🔴 🀄️ 🔗
162 寻找峰值 [✓] 数组 二分查找 🟠 🀄️ 🔗
167 两数之和 II - 输入有序数组 [✓] 数组 双指针 二分查找 🟠 🀄️ 🔗
209 长度最小的子数组 [✓] 数组 二分查找 前缀和 1+ 🟠 🀄️ 🔗
222 完全二叉树的节点个数 [✓] 位运算 二分查找 1+ 🟢 🀄️ 🔗
240 搜索二维矩阵 II [✓] 数组 二分查找 分治 1+ 🟠 🀄️ 🔗
259 较小的三数之和 🔒 [✓] 数组 双指针 二分查找 1+ 🟠 🀄️ 🔗
268 丢失的数字 [✓] 位运算 数组 哈希表 3+ 🟢 🀄️ 🔗
270 最接近的二叉搜索树值 🔒 深度优先搜索 二叉搜索树 2+ 🟢 🀄️ 🔗
275 H 指数 II [✓] 数组 二分查找 🟠 🀄️ 🔗
278 第一个错误的版本 [✓] 二分查找 交互 🟢 🀄️ 🔗
287 寻找重复数 [✓] 位运算 数组 双指针 1+ 🟠 🀄️ 🔗
300 最长递增子序列 [✓] 数组 二分查找 动态规划 🟠 🀄️ 🔗
302 包含全部黑色像素的最小矩形 🔒 深度优先搜索 广度优先搜索 数组 2+ 🔴 🀄️ 🔗
315 计算右侧小于当前元素的个数 树状数组 线段树 数组 4+ 🔴 🀄️ 🔗
327 区间和的个数 树状数组 线段树 数组 4+ 🔴 🀄️ 🔗
349 两个数组的交集 [✓] 数组 哈希表 双指针 2+ 🟢 🀄️ 🔗
350 两个数组的交集 II [✓] 数组 哈希表 双指针 2+ 🟢 🀄️ 🔗
352 将数据流变为多个不相交区间 设计 二分查找 有序集合 🔴 🀄️ 🔗
354 俄罗斯套娃信封问题 [✓] 数组 二分查找 动态规划 1+ 🔴 🀄️ 🔗
362 敲击计数器 🔒 设计 队列 数组 2+ 🟠 🀄️ 🔗
363 矩形区域不超过 K 的最大数值和 数组 二分查找 矩阵 2+ 🔴 🀄️ 🔗
367 有效的完全平方数 [✓] 数学 二分查找 🟢 🀄️ 🔗
374 猜数字大小 [✓] 二分查找 交互 🟢 🀄️ 🔗
378 有序矩阵中第 K 小的元素 [✓] 数组 二分查找 矩阵 2+ 🟠 🀄️ 🔗
400 第 N 位数字 [✓] 数学 二分查找 🟠 🀄️ 🔗
410 分割数组的最大值 贪心 数组 二分查找 2+ 🔴 🀄️ 🔗
436 寻找右区间 [✓] 数组 二分查找 排序 🟠 🀄️ 🔗
441 排列硬币 [✓] 数学 二分查找 🟢 🀄️ 🔗
456 132 模式 [✓] 数组 二分查找 2+ 🟠 🀄️ 🔗
475 供暖器 数组 双指针 二分查找 1+ 🟠 🀄️ 🔗
483 最小好进制 数学 二分查找 🔴 🀄️ 🔗
493 翻转对 树状数组 线段树 数组 4+ 🔴 🀄️ 🔗
497 非重叠矩形中的随机点 水塘抽样 数组 数学 4+ 🟠 🀄️ 🔗
528 按权重随机选择 [✓] 数组 数学 二分查找 2+ 🟠 🀄️ 🔗
532 数组中的 k-diff 数对 数组 哈希表 双指针 2+ 🟠 🀄️ 🔗
540 有序数组中的单一元素 [✓] 数组 二分查找 🟠 🀄️ 🔗
611 有效三角形的个数 [✓] 贪心 数组 双指针 2+ 🟠 🀄️ 🔗
633 平方数之和 数学 双指针 二分查找 🟠 🀄️ 🔗
644 子数组最大平均数 II 🔒 数组 二分查找 前缀和 🔴 🀄️ 🔗
658 找到 K 个最接近的元素 [✓] 数组 双指针 二分查找 3+ 🟠 🀄️ 🔗
668 乘法表中第k小的数 数学 二分查找 🔴 🀄️ 🔗
702 搜索长度未知的有序数组 🔒 数组 二分查找 交互 🟠 🀄️ 🔗
704 二分查找 [✓] 数组 二分查找 🟢 🀄️ 🔗
710 黑名单中的随机数 数组 哈希表 数学 3+ 🔴 🀄️ 🔗
713 乘积小于 K 的子数组 数组 二分查找 前缀和 1+ 🟠 🀄️ 🔗
718 最长重复子数组 数组 二分查找 动态规划 3+ 🟠 🀄️ 🔗
719 找出第 K 小的数对距离 数组 双指针 二分查找 1+ 🔴 🀄️ 🔗
729 我的日程安排表 I [✓] 设计 线段树 数组 2+ 🟠 🀄️ 🔗
731 我的日程安排表 II [✓] 设计 线段树 数组 3+ 🟠 🀄️ 🔗
732 我的日程安排表 III 设计 线段树 二分查找 2+ 🔴 🀄️ 🔗
744 寻找比目标字母大的最小字母 [✓] 数组 二分查找 🟢 🀄️ 🔗
754 到达终点数字 数学 二分查找 🟠 🀄️ 🔗
774 最小化去加油站的最大距离 🔒 数组 二分查找 🔴 🀄️ 🔗
778 水位上升的泳池中游泳 深度优先搜索 广度优先搜索 并查集 4+ 🔴 🀄️ 🔗
786 第 K 个最小的质数分数 数组 双指针 二分查找 2+ 🟠 🀄️ 🔗
792 匹配子序列的单词数 字典树 数组 哈希表 4+ 🟠 🀄️ 🔗
793 阶乘函数后 K 个零 数学 二分查找 🔴 🀄️ 🔗
825 适龄的朋友 数组 双指针 二分查找 1+ 🟠 🀄️ 🔗
826 安排工作以达到最大收益 贪心 数组 双指针 2+ 🟠 🀄️ 🔗
852 山脉数组的峰顶索引 [✓] 数组 二分查找 🟠 🀄️ 🔗
862 和至少为 K 的最短子数组 [✓] 队列 数组 二分查找 4+ 🔴 🀄️ 🔗
875 爱吃香蕉的珂珂 [✓] 数组 二分查找 🟠 🀄️ 🔗
878 第 N 个神奇数字 数学 二分查找 🔴 🀄️ 🔗
887 鸡蛋掉落 数学 二分查找 动态规划 🔴 🀄️ 🔗
888 公平的糖果交换 [✓] 数组 哈希表 二分查找 1+ 🟢 🀄️ 🔗
902 最大为 N 的数字组合 数组 数学 字符串 2+ 🔴 🀄️ 🔗
911 在线选举 设计 数组 哈希表 1+ 🟠 🀄️ 🔗
981 基于时间的键值存储 [✓] 设计 哈希表 字符串 1+ 🟠 🀄️ 🔗
1004 最大连续1的个数 III [✓] 数组 二分查找 前缀和 1+ 🟠 🀄️ 🔗
1011 在 D 天内送达包裹的能力 数组 二分查找 🟠 🀄️ 🔗
1027 最长等差数列 [✓] 数组 哈希表 二分查找 1+ 🟠 🀄️ 🔗
1044 最长重复子串 字符串 二分查找 后缀数组 3+ 🔴 🀄️ 🔗
1055 形成字符串的最短路径 🔒 贪心 双指针 字符串 1+ 🟠 🀄️ 🔗
1060 有序数组中的缺失元素 🔒 数组 二分查找 🟠 🀄️ 🔗
1062 最长重复子串 🔒 字符串 二分查找 动态规划 3+ 🟠 🀄️ 🔗
1064 不动点 🔒 数组 二分查找 🟢 🀄️ 🔗
1095 山脉数组中查找目标值 数组 二分查找 交互 🔴 🀄️ 🔗
1099 小于 K 的两数之和 🔒 数组 双指针 二分查找 1+ 🟢 🀄️ 🔗
1102 得分最高的路径 🔒 深度优先搜索 广度优先搜索 并查集 4+ 🟠 🀄️ 🔗
1146 快照数组 [✓] 设计 数组 哈希表 1+ 🟠 🀄️ 🔗
1150 检查一个数是否在数组中占绝大多数 🔒 数组 二分查找 🟢 🀄️ 🔗
1157 子数组中占绝大多数的元素 设计 树状数组 线段树 2+ 🔴 🀄️ 🔗
1170 比较字符串最小字母出现频次 数组 哈希表 字符串 2+ 🟠 🀄️ 🔗
1182 与目标颜色间的最短距离 🔒 数组 二分查找 动态规划 🟠 🀄️ 🔗
1187 使数组严格递增 数组 二分查找 动态规划 1+ 🔴 🀄️ 🔗
1198 找出所有行中最小公共元素 🔒 数组 哈希表 二分查找 2+ 🟠 🀄️ 🔗
1201 丑数 III 数学 二分查找 组合数学 1+ 🟠 🀄️ 🔗
1208 尽可能使字符串相等 字符串 二分查找 前缀和 1+ 🟠 🀄️ 🔗
1213 三个有序数组的交集 🔒 数组 哈希表 二分查找 1+ 🟢 🀄️ 🔗
1214 查找两棵二叉搜索树之和 🔒 深度优先搜索 4+ 🟠 🀄️ 🔗
1231 分享巧克力 🔒 数组 二分查找 🔴 🀄️ 🔗
1235 规划兼职工作 数组 二分查找 动态规划 1+ 🔴 🀄️ 🔗
1237 找出给定方程的正整数解 数学 双指针 二分查找 1+ 🟠 🀄️ 🔗
1268 搜索推荐系统 [✓] 字典树 数组 字符串 3+ 🟠 🀄️ 🔗
1283 使结果不超过阈值的最小除数 数组 二分查找 🟠 🀄️ 🔗
1292 元素和小于等于阈值的正方形的最大边长 数组 二分查找 矩阵 1+ 🟠 🀄️ 🔗
1300 转变数组后最接近目标值的数组和 数组 二分查找 排序 🟠 🀄️ 🔗
1337 矩阵中战斗力最弱的 K 行 [✓] 数组 二分查找 矩阵 2+ 🟢 🀄️ 🔗
1346 检查整数及其两倍数是否存在 [✓] 数组 哈希表 双指针 2+ 🟢 🀄️ 🔗
1348 推文计数 设计 哈希表 二分查找 2+ 🟠 🀄️ 🔗
1351 统计有序矩阵中的负数 [✓] 数组 二分查找 矩阵 🟢 🀄️ 🔗
1385 两个数组间的距离值 [✓] 数组 双指针 二分查找 1+ 🟢 🀄️ 🔗
1428 至少有一个 1 的最左端列 🔒 数组 二分查找 交互 1+ 🟠 🀄️ 🔗
1439 有序矩阵中的第 k 个最小数组和 数组 二分查找 矩阵 1+ 🔴 🀄️ 🔗
1477 找两个和为目标值且不重叠的子数组 数组 哈希表 二分查找 2+ 🟠 🀄️ 🔗
1482 制作 m 束花所需的最少天数 数组 二分查找 🟠 🀄️ 🔗
1483 树节点的第 K 个祖先 深度优先搜索 广度优先搜索 3+ 🔴 🀄️ 🔗
1488 避免洪水泛滥 贪心 数组 哈希表 2+ 🟠 🀄️ 🔗
1498 满足条件的子序列数目 [✓] 数组 双指针 二分查找 1+ 🟠 🀄️ 🔗
1508 子数组和排序后的区间和 数组 双指针 二分查找 1+ 🟠 🀄️ 🔗
1521 找到最接近目标值的函数值 位运算 线段树 数组 1+ 🔴 🀄️ 🔗
1533 找到最大整数的索引 🔒 数组 二分查找 交互 🟠 🀄️ 🔗
1539 第 k 个缺失的正整数 [✓] 数组 二分查找 🟢 🀄️ 🔗
1552 两球之间的磁力 数组 二分查找 排序 🟠 🀄️ 🔗
1562 查找大小为 M 的最新分组 数组 哈希表 二分查找 1+ 🟠 🀄️ 🔗
1574 删除最短的子数组使剩余数组有序 [✓] 数组 双指针 2+ 🟠 🀄️ 🔗
1608 特殊数组的特征值 [✓] 数组 二分查找 排序 🟢 🀄️ 🔗
1618 找出适应屏幕的最大字号 🔒 数组 字符串 二分查找 1+ 🟠 🀄️ 🔗
1631 最小体力消耗路径 深度优先搜索 广度优先搜索 并查集 4+ 🟠 🀄️ 🔗
1648 销售价值减少的颜色球 贪心 数组 数学 3+ 🟠 🀄️ 🔗
1649 通过指令创建有序数组 树状数组 线段树 数组 4+ 🔴 🀄️ 🔗
1658 将 x 减到 0 的最小操作数 数组 哈希表 二分查找 2+ 🟠 🀄️ 🔗
1671 得到山形数组的最少删除次数 [✓] 贪心 数组 二分查找 1+ 🔴 🀄️ 🔗
1712 将数组分成三个子数组的方案数 数组 双指针 二分查找 1+ 🟠 🀄️ 🔗
1713 得到子序列的最少操作次数 贪心 数组 哈希表 1+ 🔴 🀄️ 🔗
1739 放置盒子 贪心 数学 二分查找 🔴 🀄️ 🔗
1751 最多可以参加的会议数目 II 数组 二分查找 动态规划 1+ 🔴 🀄️ 🔗
1760 袋子里最少数目的球 [✓] 数组 二分查找 🟠 🀄️ 🔗
1782 统计点对的数目 数组 双指针 2+ 🔴 🀄️ 🔗
1793 好子数组的最大分数 数组 双指针 2+ 🔴 🀄️ 🔗
1802 有界数组中指定下标处的最大值 贪心 二分查找 🟠 🀄️ 🔗
1818 绝对差值和 数组 二分查找 有序集合 1+ 🟠 🀄️ 🔗
1838 最高频元素的频数 贪心 数组 二分查找 3+ 🟠 🀄️ 🔗
1847 最近的房间 数组 二分查找 有序集合 1+ 🔴 🀄️ 🔗
1851 包含每个查询的最小区间 数组 二分查找 排序 2+ 🔴 🀄️ 🔗
1855 下标对中的最大距离 数组 双指针 二分查找 🟠 🀄️ 🔗
1862 向下取整数对和 数组 数学 二分查找 1+ 🔴 🀄️ 🔗
1870 准时到达的列车最小时速 数组 二分查找 🟠 🀄️ 🔗
1885 统计数对 🔒 数组 双指针 二分查找 1+ 🟠 🀄️ 🔗
1889 装包裹的最小浪费空间 数组 二分查找 前缀和 1+ 🔴 🀄️ 🔗
1891 割绳子 🔒 数组 二分查找 🟠 🀄️ 🔗
1894 找到需要补充粉笔的学生编号 数组 二分查找 前缀和 1+ 🟠 🀄️ 🔗
1898 可移除字符的最大数目 数组 双指针 字符串 1+ 🟠 🀄️ 🔗
1901 寻找峰值 II 数组 二分查找 矩阵 🟠 🀄️ 🔗
1918 第 K 小的子数组和 🔒 数组 二分查找 滑动窗口 🟠 🀄️ 🔗
1923 最长公共子路径 数组 二分查找 后缀数组 2+ 🔴 🀄️ 🔗
1932 合并多棵二叉搜索树 深度优先搜索 哈希表 2+ 🔴 🀄️ 🔗
1954 收集足够苹果的最小花园周长 数学 二分查找 🟠 🀄️ 🔗
1956 感染 K 种病毒所需的最短时间 🔒 几何 数组 数学 2+ 🔴 🀄️ 🔗
1964 找出到每个位置为止最长的有效障碍赛跑路线 [✓] 树状数组 数组 二分查找 🔴 🀄️ 🔗
1966 未排序数组中的可被二分搜索的数 🔒 数组 二分查找 🟠 🀄️ 🔗
1970 你能穿过矩阵的最后一天 深度优先搜索 广度优先搜索 并查集 3+ 🔴 🀄️ 🔗
2008 出租车的最大盈利 数组 哈希表 二分查找 2+ 🟠 🀄️ 🔗
2009 使数组连续的最少操作数 数组 哈希表 二分查找 1+ 🔴 🀄️ 🔗
2024 考试的最大困扰度 字符串 二分查找 前缀和 1+ 🟠 🀄️ 🔗
2031 1 比 0 多的子数组个数 🔒 树状数组 线段树 数组 4+ 🟠 🀄️ 🔗
2035 将数组分成两个数组并最小化数组和的差 位运算 数组 双指针 4+ 🔴 🀄️ 🔗
2040 两个有序数组的第 K 小乘积 数组 二分查找 🔴 🀄️ 🔗
2054 两个最好的不重叠活动 [✓] 数组 二分查找 动态规划 2+ 🟠 🀄️ 🔗
2055 蜡烛之间的盘子 数组 字符串 二分查找 1+ 🟠 🀄️ 🔗
2064 分配给商店的最多商品的最小值 [✓] 数组 二分查找 🟠 🀄️ 🔗
2070 每一个查询的最大美丽值 [✓] 数组 二分查找 排序 🟠 🀄️ 🔗
2071 你可以安排的最多任务数目 贪心 队列 数组 3+ 🔴 🀄️ 🔗
2080 区间内查询数字的频率 设计 线段树 数组 2+ 🟠 🀄️ 🔗
2089 找出数组排序后的目标下标 [✓] 数组 二分查找 排序 🟢 🀄️ 🔗
2106 摘水果 数组 二分查找 前缀和 1+ 🔴 🀄️ 🔗
2111 使数组 K 递增的最少操作次数 数组 二分查找 🔴 🀄️ 🔗
2137 通过倒水操作让所有的水桶所含水量相等 🔒 数组 二分查找 🟠 🀄️ 🔗
2141 同时运行 N 台电脑的最长时间 贪心 数组 二分查找 1+ 🔴 🀄️ 🔗
2179 统计数组中好三元组数目 树状数组 线段树 数组 4+ 🔴 🀄️ 🔗
2187 完成旅途的最少时间 数组 二分查找 🟠 🀄️ 🔗
2223 构造字符串的总得分和 字符串 二分查找 字符串匹配 3+ 🔴 🀄️ 🔗
2226 每个小孩最多能分到多少糖果 [✓] 数组 二分查找 🟠 🀄️ 🔗
2234 花园的最大总美丽值 贪心 数组 双指针 2+ 🔴 🀄️ 🔗
2250 统计包含每个点的矩形数目 树状数组 数组 二分查找 1+ 🟠 🀄️ 🔗
2251 花期内花的数目 数组 哈希表 二分查找 3+ 🔴 🀄️ 🔗
2258 逃离火灾 广度优先搜索 数组 二分查找 1+ 🔴 🀄️ 🔗
2271 毯子覆盖的最多白色砖块数 贪心 数组 二分查找 2+ 🟠 🀄️ 🔗
2286 以组为单位订音乐会的门票 设计 树状数组 线段树 1+ 🔴 🀄️ 🔗
2300 咒语和药水的成功对数 [✓] 数组 双指针 二分查找 1+ 🟠 🀄️ 🔗
2302 统计得分小于 K 的子数组数目 数组 二分查找 前缀和 1+ 🔴 🀄️ 🔗
2332 坐上公交的最晚时间 数组 双指针 二分查找 1+ 🟠 🀄️ 🔗
2333 最小差值平方和 贪心 数组 二分查找 2+ 🟠 🀄️ 🔗
2354 优质数对的数目 位运算 数组 哈希表 1+ 🔴 🀄️ 🔗
2358 分组的最大数量 贪心 数组 数学 1+ 🟠 🀄️ 🔗
2387 行排序矩阵的中位数 🔒 数组 二分查找 矩阵 🟠 🀄️ 🔗
2389 和有限的最长子序列 贪心 数组 二分查找 2+ 🟢 🀄️ 🔗
2398 预算内的最多机器人数目 队列 数组 二分查找 4+ 🔴 🀄️ 🔗
2411 按位或最大的最小子数组长度 位运算 数组 二分查找 1+ 🟠 🀄️ 🔗
2424 最长上传前缀 并查集 设计 树状数组 4+ 🟠 🀄️ 🔗
2426 满足不等式的数对数目 树状数组 线段树 数组 4+ 🔴 🀄️ 🔗