题单广场 /

【CSP-J】二分法

算法专题
0/19已通过

题单简介

利用单调性缩小范围,练习二分查找与二分答案。 专题题单已建立,题目由团队负责人后续选入。 首批教学配套 普通二分 学习难度:3~3(九级标准)。 知识目标与评价 必学:有序查找与二分边界。 先备:理解非降序、有重复值、位置范围和基本复杂度;不把普通二分和答案二分混为一题。 每次明确要找“第一个≥x”还是“最后一个≤x”。统一半开区间[l,r),空区间终止;相等分支决定重复值的左右边界。最近刻度先定位,再比较两侧,平局按题意选较小者。 学习与练习顺序 1. 用[1,1,1]查询0、1、2,手算三个任务的不同答案。 2. 检查空表(最近刻度不允许空表)、单元素、目标小于全部或大于全部的情况。 3. n、q可达100000,估算每次扫描与对数查询的总操作次数,不能只在小样例上跑通。 配套练习 - 第一张不小于目标的卡片(P01012,难度3)。 - 最后一张不大于目标的卡片(P01015,难度3)。 - 找到最近的刻度(P01014,难度3)。 原题单保留:【CSP-J】二分法。原Training只有“测试训练”,本轮不将其当作正式教学配套,也不伪造训练引用。 自查与评价边界 能解释区间不变量、相等分支和不存在时的返回值。先保留普通有序查找练习;答案二分另学单调判定,本轮未将其难度目标混入。 配套数量按每目标、每个已知难度、不同源题分别核对;当前政策默认3道自主/轻提示通过,普通内容浏览和教学自查不会产生掌握事实。个人已做题、权限及活动状态另由运行时复核;源题不同不代表题族独立。 延后练习 隔两天不标“二分”,给查询故事和数据范围,让学生判断是否可以利用有序性并说明原因。 本题单保留原有题目,新增配套以当前权限和正式映射为准;不会因浏览题单自动修改学习状态。 练习入口:切换到本题单的“题目列表”,按上述题号打开练习;原题保留,可按基础选练。