二分模板
模板 二分
2023-09-27 14:28:13 时间
理解
1、check(int x)
检查x是否满足某种性质
2、模板1为:满足条件向左逼近,不满足条件向右逼近。如果有多个满足条件的数据,返回最左边那个。
3、模板2为:满足条件向右逼近,不满足条件向左逼近。如果有多个满足条件的数据,返回最右边那个。
4、yxc大佬的模板,适用于二分查找和二分答案。
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
相关文章
- POJ2446 模板盖格子 简单二分匹配
- (尚003).Vue_模板语法
- flask基础之jijia2模板使用基础(二)
- 12款非常精致的免费 HTML5 & CSS3 网站模板
- 【前端模板之路】一、重构的兄弟说:我才不想看你的代码!把HTML给我交出来!
- 【HDU 2063】过山车(二分图最大匹配模板题)
- 【转】模板的全特化与偏特化
- koa 基础(九) ejs 模板引擎的使用
- 调研js模板引擎
- 《iOS应用开发》——1.4节修改模板
- [模板题][双指针]数组元素的目标和
- php模板原理PHP模板引擎smarty模板原理浅谈
- 【蓝桥杯Java组】送你一个不会出错的二分搜索模板
- SpringBoot导出Word方式一:根据Word模板动态生成word(Poi-tl)
- 单页面响应式模板:黑石
- Django之模板(六)